内存

内存

1.内存的基础知识

1.内存

1.内存

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

2.内存地址

在多道程序环境下，系统中会有多个程序并发执行，也就是说会有多个程序的数据需要同时放到内存中。那么如何区分各个程序的数据是放在哪儿呢？------》给内存编址

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

2）如果计算机按字节编址，即每个存储单元大小为1字节，即1B，即8个比特位

3）如果字长为16位的计算机“按字”编址，则每个内存单元大小为1个字；每个字的大小为16个二进制位

3.注意：

内存大小4GB，则表示该内存中可以存放4*2^30个字节。

2.进程的运行原理——指令

1、指令存放在程序段、进程的数据存放在数据段

2、我们写的代码要翻译成CPU能识别的指令。这些指令告诉CPU应该去内存的那个地址存/取数据，这个数据应该做什么样的处理。编译时给出的地址是逻辑地址

3.逻辑地址&物理地址

编译时产生的指令只关心“相对地址”，实际放入内存时，再想办法根据进程的起始位置得到绝对地址

1、逻辑地址，又称相对地址，往往地址从0开始编号

2、物理地址，又称绝对地址，数据实际存入内存时的地址

3、地址变化过程如下图：

2.装入模块装入内存

1.装入的三种方式

完成逻辑地址到物理地址的转化

1.绝对装入

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

2、缺点：绝对装入只适用于单道程序环境

3、程序中使用的绝对地址，可在编译或者汇编的时候给出，也可由程序员直接赋予。通常情况下都是编译或汇编时再转换为绝对地址

2.静态重定位

1）静态重定位

又称可重定位装入。编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存当前的情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）

2）特点

一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦装入内存后，在运行期间就不能再移动，也不能再申请内存空间。

3.动态重定位

1）动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。

2）采用动态重定位时允许程序在内存中发生移动。

3）优点：

可以将程序分配到不连续的存储区；在程序运行前只需装入它的部分代码即可投入运行，然后再程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。

3.链接的三种方式

1.静态链接

在程序运行之前，先将各目标模块以及它们所需要的库函数连接成一个完整的可执行文件（装入模块）后不再拆开

2.装入时动态链接

将个目标模块装入内存时，边装入边链接的链接方式

3运行时动态链接

在程序执行中需要该目标模块时，才对它进行链接。

优点是：便于修改和更新，便于实现对目标模块的共享，用不到的模块不再需要装入内存

注意：链接完成会形成完整的逻辑地址，装入完成会形成完整的物理地址

4.内存管理

1.OS需要实现的功能

1.内存空间的分配与回收

​ 操作系统负责内存空间的分配与回收

2.对内存空间进行扩充

​ 操作系统需要提供某种技术从逻辑上对内存空间进行扩充

3.地址装换

​ 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换

                     具体的转换是在装入时实现的。

4.内存保护

​ 操作系统需要提供内存保护的功能，保证各进程在各自存储空间内运行，互不干扰

2.实现内存保护

1.方式1：

在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查首付越界

2.方式2：

采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。

重定位寄存器中存放的是进程的起始物理地址。

界地址寄存器中存放的是进程的最大逻辑地址

如下图：

3.实现内存扩充

1.覆盖技术

1）原因：早期的计算机内存很小，因此经常会出现内存大小不够用的情况。

2）人们引入了覆盖技术，用来解决“程序大小超过物理内存总和”的问题

3）思想：将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。内存中分为一个“固定区”和若干个“覆盖区”。需要常驻内存的段放在“固定区“中，调入后就不再调出（除非运行结束）；不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。

4）如下图：

2.交换技术

1）思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

2）中级调度（内存调度）就是为了实现交换技术而产生的一种策略；决定将哪个处于挂起状态的进程重新调入内存。

3）暂时换出外存等待的进程状态称为挂起状态，进一步可以细分为就绪挂起和阻塞挂起。虽然进程会被换出内存，但PCB需要常驻内存，保存进程的相关信息。

4）相关问题如下图：

3.虚拟存储技术

虚拟技术后面单独讲

4.覆盖技术和交换技术的区别

1）覆盖是在同一程序或进程中的

2）交换是在不同进程（或作业）之间的

4.内存空间的分配与回收

连续分配：指为用户进程分配的必须是一个连续的内存空间

1.连续分配管理方式

1）单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区，系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。

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

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

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

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

2）固定分区分配

a、为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中装入一道作业，这样就形成了最早的、最简单的一种运行多道程序的内存管理方式。

b、固定分区分配：分区大小相等、分区大小不等

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

d、分区大小不等：增加了灵活性，可以满足不同大小的进程需求。

如下图

e、操作系统需要建立一个数结构——分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）

3）动态分区分配

如果需要回收的前、后、前后均有空闲分区的话，合并成一个大的分区，并修改相关表项

内部碎片和外部碎片

5.动态分区分配算法-内存空间分配与回收

问题：在动态分区分配方式中，当多个空闲分区都能满足要求时，应该选择哪个分区进行分配？

1.首次适应算法(First Fit)

1.算法思想

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

2.如何实现

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

2.最佳适应算法(Best Fit)

1.算法思想

由于动态分区分配是一种连续的分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程“到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区。

2.如何实现

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

3.缺点

每次都选取最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方式会产生很多外部碎片。

3.最坏适应算法(Worst Fit)

1.算法思想

为了解决最佳适应算法的问题——留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

2.如何实现

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

3.缺点：

每次都选虽大的分区进行分配，虽然可以让分配后留下的空闲分区更大，更可用，但是这种方式会导致较大的连续空闲分区被快速用完。如果有大进程到达，就没有内存分区可以用了

4.邻近适应算法(Next Fit)

如下图：

5.总结

总览：

6.基本分页存储管理

连续分配：为用户进程分配的必须是一个连续的内存空间

非连续分配：为用户进程分配的可以是一些分散的内存空间

1.分页存储管理的基本概念

2.如何实现地址转换

3.逻辑地址结构

4.怎么找到每个页在内存中的存放位置

注意：页号是隐含的

5.基本地址变换机构

1、基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址

2、通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。

3、进程未执行时，页表的始址和页表的长度放在进程控制块PCB中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

注意：页表中存放的是内存块号，内存按照页表的大小分成了若干块，所以只需要直到内存块号即可知道该块的实际物理地址

4、例题

5、页表的进一步讨论

6.具有快表的地址变换机构

1、局部性原理

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

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

2、在基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项，因此，引入快表机制，以减少访问内存中页表的次数。

3、快表TLB

快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

4、引入快表后，地址变换过程

5、总结

7.两级页表

1.单级页表存在的问题

问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框，违背了离散分配内存的思想

问题二：根据程序的局部性原理，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

2.单级页表存在问题的解决方式

1）可以将长的页表进行分组，使得每个内存刚好可以放入一个分组（比如上个例子中，页面大小4KB，每个页表项4B，每个页面可以存放1K个页表项，因此每1K个连续的页表项为一组，每组刚好占一个内存块，再将各组离散的放到各个内存块中；单级页表的大小为2^20B，因此可以分为 1024个分组，如下图所示）

2）另外，要为离散分配的页表建立一张页表，称为页目录表，或称外层页表，或称顶层页表。

3）问题二的解决方式：可以在需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存；若访问的页面不在内存中，则产生缺页中断（内中断），然后将目标页面从外存调入内存

3.二级页表实现逻辑地址转换为物理地址

4.注意

1）若采用多级页表机制，则各级页表的大小不能超过一个页面

2）两级页表的访存次数分析

7.基于分段存储管理方式

基本分段存储管理，与”分页“最大的区别就是——离散分配时所分配地址空间的基本单位不同

1.分段

1、进程的地址空间，按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址

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

3、分段系统的逻辑结构由段号和段内地址（偏移量）组成。如下：

2.段表

3.地址变换

1.进程切换，相关的内核程序负责恢复进程运行环境，将进程中的数据复制到段表寄存器；（段表始址F，段表长度M）

4.分页、分段管理的对比

5.对比总结

8.段页式管理方式

1.分页、分段管理方式中的最大优缺点

2.段页式

先对逻辑地址分段，再对分段后的逻辑地址分页，通过页表机制转换为实际的物理地址

3.段页式管理的逻辑地址结构

4.段表、页表

5.逻辑地址转换为物理地址过程

9.虚拟存储技术-内存空间扩充

1.虚拟内存的基本概念

1.传统存储管理方式的特征、缺点

1）一次性

作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：a、作业很大时，不能全部装入内存，导致大作业无法运行；b、当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序的并发度下降。

2）驻留性

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

可以通过虚拟技术解决以上问题

2.局部性原理

1）时间局部性、空间局部性

2）高速缓冲技术的思想：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。

3）基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。在程序执行过程中，当所访问的信息不在内存时，有操作系统负责将所需信息从外存调入内存，然后继续执行程序。如果内存空间不够，有操作系统负责将内存中暂时用不到的信息换出到外存。在操作系统的管理下，在用户看来似乎有一个比实际大的内存，这就是虚拟内存。

4）虚拟内存有一下三个特征：

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

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

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

5）注意：

2.怎么实现虚拟内存技术

虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

1、请求分页存储管理（主要学）

2、请求分段存储管理

3、请求段页式存储管理

4、注意：

虚拟内存技术区别于传统存储管理的点在于：

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

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

3）为了实现上述功能，操作系统需要提供请求调页（请求调段）功能、页面置换功能

10.请求分页存储管理方式

1.页表机制

1、与基本分页管理相比，请求分页管理中，为了实现”请求调页“，操作系统需要知道每个页面是否已经调入内存：如果还没调入，那么需要知道该页面在外存中存放的位置。

2、当内存空间不够时，需要实现”页面置换“，操作系统需要通过某些指标来决定到底换出哪个页面；有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。

3、请求分页存储管理的页表

2.缺页中断机构

1、在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

2、如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改也表中相应的页表项。如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

3、缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断。一条指令在执行期间，可能产生多次缺页中断。

4、中断复习：

3.地址变换机构

请求分页存储管理区别于基本分页存储管理，新增以下步骤

1、请求调页（查到页表项时进行判断）

2、页面置换（需要调入页面，但没有空闲内存块时进行）

3、需要修改请求页表中新增的表项

过程如下：

注意1：快表中有的页面一定是在内存中，若某个页面被换出外存，则快表中的相应表项也要删除，否则可能访问错误的页面

注意2：在具有快表机构的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是：查快表（未命中）——查慢表（发现未调入内存）——调页（调入的页面对应的表项会直接加入快表）——查快表（命中）——访问目标内存单元。

11.页面置换算法

页面的换入、换出需要磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率

1.最佳置换算法（OPT）

注意，页面置换算法的前提是知道接下来即将访问的页面序列，但在实际上，只有在进程执行的过程中才能知道接下来会访问到哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

2.先进先出置换算法（FIFO)

访问序列未变，分配4个内存块：

3.最近最久未使用置换算法（LRU）

4.时钟置换算法（CLOCK）

缺点：只考虑了一个页面是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O次奥做写回外存。只有被淘汰的页面被修改过，才需要写回外存。

5.改进型的时钟置换算法

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

2、在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。

3、增加修改位，修改位=0表示页面没有被修改过，修改位=1表示页面被修改过

4、为方便讨论，下图使用（访问位，修改位）的形式表示各页面的状态。如（1，1）表示一个页面近期被访问过，且被修改过。

6.总结

12.页面分配策略

在虚拟存储技术中，根据局部性原理，进程没必要一次性全部将数据加载到内存，因此只需要加载一部分。那么给进程分配多大空闲物理块，可以使得缺页率较低，减少I/O次数，就是本节讨论的问题

1.驻留集

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

2、采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

1）若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际应用于进程推进的时间很少；

2）驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

2.分配、置换策略

1.固定分配

操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变

2.可变分配

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

3.局部置换

发生缺页时，只能选择自己的物理块进行置换。

4.全局置换

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

5.分配、置换策略

3.何时调入页面

4.从何处调入页面

5.抖动现象

1、刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动或颠簸。产生抖动的主要原因是进程频繁访问的页面数目大于可用的物理块数（分配给进程的物理块不够）

2、为进程分配的物理块太少，会使进程发生抖动现象。为进程分配物理块太多，又会降低系统整体的并发度，降低某些资源的利用率。

3、为解决上述问题，提出了“工作集”的概念

6.进程工作集

工作集的大小是动态的，会发生变化。