第六章 内存
6.1 内存的基本知识
1.什么是内存，有什么作用？
内存（Memory），也称为主存储器，是计算机中用于暂时存储数据和指令的硬件设备。内存的主要作用包括：
存储执行中的程序：操作系统和正在运行的应用程序需要存储在内存中才能被CPU访问和执行。
数据缓存：内存用于临时存储处理过程中的数据，以便快速读写。
交换空间：内存可以作为与其他存储设备（如硬盘）交换数据的缓冲区。
2. 进程运行的基本原理
指令的工作原理
进程的运行基于一系列指令，这些指令是CPU执行的基本操作。指令的工作原理如下：
取指令：CPU从内存中取出下一条指令。
解码：CPU解码指令，确定需要执行的操作。
执行：CPU执行指令指定的操作，这可能包括算术计算、数据传输或控制操作。
重复：CPU重复上述步骤，直到程序结束。
逻辑地址VS物理地址
逻辑地址：也称为虚拟地址，是由CPU生成的地址，是程序员视角下的地址空间。逻辑地址空间是连续的，不受物理内存大小的限制。
物理地址：是内存单元的实际地址，是数据实际存储在内存中的位置。
如何实现地址转换
地址转换通常通过以下步骤实现：
分段：将逻辑地址空间分为多个段，如代码段、数据段等。
分页：将每个段进一步划分为固定大小的页。
地址映射：操作系统维护一个页表，将逻辑地址（段号+页号+偏移量）映射到物理地址（帧号+偏移量）。
转换：CPU访问内存时，内存管理单元（MMU）根据页表进行地址转换。
从写程序到程序运行的过程
编写代码：程序员使用高级编程语言编写源代码。
编译：源代码通过编译器转换成机器代码，生成可执行文件。
加载：操作系统将可执行文件从硬盘加载到内存中。
地址映射：操作系统为程序分配逻辑地址空间，并设置页表以进行地址转换。
执行：CPU开始执行程序的指令，程序进入运行状态。
调度：操作系统根据调度算法决定何时让程序运行，以及何时切换到其他程序。
结束：程序执行完毕或被终止，操作系统回收分配给程序的资源。
整个过程涉及到操作系统的内存管理、进程管理、文件系统等多个组件的协同工作。
6.2 内存管理的概念
1.内存空间的分配与回收
内存空间的分配与回收是由操作系统负责的，主要过程如下：
分配
请求分配：当进程需要内存时，它会向操作系统发出内存分配请求。
查找空闲内存：操作系统通过内存管理算法查找足够的空闲内存块来满足进程的请求。
分配内存：操作系统将找到的空闲内存块分配给进程，并更新内存分配表。
初始化：分配给进程的内存空间通常会被初始化，以确保数据的一致性。
连续分配管理方式
单一连续分配是最简单的内存分配方式，它的特点如下：
整个物理内存：在单一连续分配方式下，整个物理内存被一个进程独占。
无内存浪费：由于整个内存被一个进程使用，因此没有内部碎片。
系统简单：适用于单用户单任务操作系统，如早期的DOS系统。
限制性：无法同时运行多个程序，系统的资源利用率低。
固定分区分配将物理内存划分为若干个固定大小的分区，每个分区可以分配给一个进程。其特点包括：
多个分区：内存被划分为若干个固定大小的分区，每个分区大小相等或根据不同的需求设置不同大小。
减少内存浪费：与单一连续分配相比，可以同时运行多个进程。
内部碎片：每个分区的大小是固定的，如果进程需要的内存小于分区大小，会导致内部碎片。
管理简单：操作系统只需维护一个空闲分区表，当有进程请求内存时，只需在表中查找合适的分区分配。
动态分区分配是在进程请求内存时，根据进程的大小动态地分配内存块。这种方式的特点包括：
按需分配：分配给进程的内存块大小正好等于进程需求的大小，减少了内部碎片。
外部碎片：随着时间的推移，内存中可能会出现许多小的空闲块，导致无法分配给需要较大内存空间的进程。
复杂的管理：操作系统需要维护空闲内存块链表，并实现内存分配和回收的算法，如首次适应、最佳适应、最坏适应等。
内存紧凑：可能需要通过内存紧凑（或称为碎片整理）来减少外部碎片，但这通常是一个耗时的过程。
非连续分配管理方式
基本分页存储管理（Paging）
原理：将物理内存和逻辑内存划分为固定大小的块，称为页（Page）和页框（Page Frame）。操作系统为每个进程维护一个页表，记录逻辑页与物理页框的映射关系。
特点：
固定大小：页的大小是固定的，通常是2的幂。
地址映射：逻辑地址被分为页号和页内偏移。通过页表将逻辑页映射到物理页框。
无需连续：物理内存不需要连续，只要页表中有相应的映射即可。
内部碎片：由于页的大小固定，可能会产生内部碎片，即页框中未使用的空间。
页表只需要记录真实的其实地址。
基本分段存储管理（Segmentation）
原理：将逻辑地址空间划分为若干个大小不等的段（Segment），每个段代表程序的一部分，如代码段、数据段等。每个段有一个段名和大小，操作系统为每个进程维护一个段表，记录段的基地址和长度。
特点：
可变大小：每个段的大小可以不同，根据程序的需要而定。
地址映射：逻辑地址由段号和段内偏移组成。通过段表将逻辑段映射到物理内存。
信息保护：可以很容易地实现段的保护和共享。
外部碎片：由于段的大小不同，可能会产生外部碎片，即内存中无法被利用的小空闲块。
记录段长和基址
段页式存储管理（Segmented Paging）
原理：结合了分页和分段的特点，先将逻辑地址空间划分为段，每个段再划分为固定大小的页。每个段有一个段表，每个页有一个页表，形成两级映射。
特点：
两级映射：先通过段表找到页表，再通过页表找到物理地址。
减少碎片：通过分页减少了内部碎片，通过分段减少了外部碎片。
灵活性和保护：分段提供了灵活性和保护机制，分页提供了简单的地址映射。
复杂性：管理较复杂，需要维护两级映射表，增加了内存管理的开销。
回收
释放请求：当进程不再需要内存时，或者进程结束时，它会释放内存。
更新内存表：操作系统更新内存分配表，将释放的内存标记为空闲。
合并空闲块：操作系统可能需要合并相邻的空闲内存块，以减少内存碎片。
2.内存空间的扩充
内存空间的扩充可以通过以下方式实现：
覆盖技术（一般不用了）
将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。
内存中分为一个“固定区”和若干个“覆盖区”。
需要常驻内存的段放在“固定区”中，调入就不再调出（除非运行结束）
不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。
虚拟内存
分页：操作系统使用分页技术，将物理内存扩展到硬盘上的交换空间。
交换(Swapping)：操作系统将不常用的页从物理内存交换到硬盘上的交换文件，以释放物理内存。(保留PCB信息，换出进程！)
具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件空间的管理采用离散分配方式；对换区空间只占磁盘空间很小的一部分。被换出的进程数据就存放在对换区。由于兑换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此对换区采用连续分配方式。
硬件扩充
增加内存条：通过增加更多的内存条来物理上增加内存容量。
内存映射：使用内存映射技术，将外部存储设备映射到内存地址空间。
3. 地址转换
地址转换是由内存管理单元（MMU）完成的，过程如下：
逻辑地址到线性地址：如果使用了分段，首先将逻辑地址（段:偏移）转换为线性地址。
线性地址到物理地址：通过页表将线性地址转换为物理地址。这通常涉及以下步骤：
查找页表：根据线性地址中的页号查找页表。
获取帧号：从页表中获取对应的帧号。
计算物理地址：将帧号与线性地址中的页内偏移结合，形成物理地址。
地址重定位
绝对装入：编译时产生绝对地址。（单道程序阶段）
可重定位装入：装入时将逻辑地址转换为物理地址。（多道批处理）
动态运行时装入：运行时将逻辑地址转换为物理地址，需设置重定位寄存器。（现代操作系统）
快表
快表，又称联想寄存器（TLB， translation lookaside buffer）,是一种访问速度比内存快很多的高速缓存（TLB不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应的页表称为慢表。
两级页表
单级页表问题：
页表必须连续存放，因此当夜表很大时，需要占用很多个连续的页框。
没有必要让整个页表常驻内存，因为进程在一段时间内可以只需要访问某个特定的页面。
将进程地址空间分页，并为其建立一张页表，记录各页面的存放位置。
注意
多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级。
多级页表的访存次数（假设没有快表机构）--N级页表访问一个逻辑地址需要N+1次访存。
存储保护
存储保护是操作系统确保每个进程只能访问它被授权访问的内存区域的过程。以下是几种常见的存储保护机制：
两种方式
设置上下限寄存器。
利用重定位寄存器，界地址寄存器进行判断。
访问控制
访问权限：操作系统为每个内存页设置访问权限（读、写、执行）。
用户/内核模式：CPU运行在用户模式或内核模式，以限制对系统资源的访问。
地址空间隔离
虚拟内存：每个进程都有自己的虚拟地址空间，相互隔离。
页表保护：页表中的条目可以设置保护位，以防止对内存页的未授权访问。
异常处理
内存访问违规：当进程尝试访问未被授权的内存时，MMU会产生一个异常，操作系统会捕获这个异常并采取行动，通常是终止进程。
通过这些机制，操作系统可以保护内存免受错误程序或恶意软件的破坏，确保系统的稳定性和安全性。
6.3 动态分区分配算法
动态分区分配算法是操作系统在动态分配内存时使用的策略，以决定如何从空闲内存块中选择一个分区来满足进程的内存请求。以下是四种常见的动态分区分配算法：
1.首次适应算法（First Fit）
原理：操作系统从空闲内存块的开始位置查找，直到找到一个足够大的空闲块来满足进程的请求。
操作：维护一个空闲内存块的链表，按地址递增的顺序排列。分配时从链表头开始查找。
优点：简单，快速，因为通常在链表的前端就能找到合适的空闲块。
缺点：可能导致内存的低端区域出现很多小的空闲块，造成外部碎片。
2.最佳适应算法（Best Fit）
原理：操作系统查找所有足够大的空闲块，并选择最小的那个来分配给进程，以尽可能减少剩余空闲块的大小。
操作：维护一个所有空闲块的链表，按大小递增的顺序排列。分配时查找链表，找到最小且足够大的块。
优点：最小化剩余空闲块的大小，减少了外部碎片。
缺点：可能导致很多小的空闲块，增加了管理开销，并且可能会因为频繁的分割和合并操作导致性能下降。
3.最坏适应算法（Worst Fit）
原理：与最佳适应算法相反，操作系统查找所有足够大的空闲块，并选择最大的那个来分配给进程。
操作：维护一个所有空闲块的链表，按大小递减的顺序排列。分配时查找链表，找到最大且足够大的块。
优点：可能会减少分割操作，因为剩余的空闲块通常较大。
缺点：可能导致非常大的空闲块被分割，造成较大的外部碎片。
4.临近适应算法（Next Fit）
原理：这是首次适应算法的一个变种，不同之处在于它不是从链表头开始查找，而是从上次分配结束的地方开始查找。
操作：维护一个空闲内存块的链表，按地址递增的顺序排列。分配时从上次分配结束的下一个空闲块开始查找。
优点：可以减少查找时间，因为不会重复检查已经检查过的空闲块。
缺点：可能导致内存分配的不均匀，因为搜索可能集中在内存的某个区域。
每种算法都有其特定的使用场景和权衡。例如，首次适应算法通常比最佳适应算法快，但可能产生更多的碎片。最佳适应算法可以最小化碎片，但可能需要更多的时间来维护和搜索空闲块。最坏适应算法可能产生很多小空闲块，但剩余的大空闲块有助于后续分配较大的内存请求。临近适应算法在实现上简单，但可能不如首次适应算法那样高效。
6.4 虚拟内存
1.基本概念
传统存储管理方式的特征和缺点
特征
连续性：程序在内存中占用连续的地址空间。
单一性：在单一连续分配方式中，整个内存被一个进程独占。
固定分配：在固定分区分配方式中，内存被划分为若干固定大小的区域。
缺点
内部碎片：在固定分区分配中，分配的内存可能比实际需要的大，导致内存浪费。
外部碎片：在动态分区分配中，内存碎片化可能导致无法分配给需要较大连续内存空间的进程。
低效的内存利用：由于碎片的存在，内存的利用率可能不高。
限制进程大小：进程的大小受限于物理内存的大小。
局部性原理
时间局部性
概念：如果一个信息项被访问，那么它在不久的将来很可能再次被访问。
应用：利用缓存技术，如CPU缓存，来存储最近访问的数据和指令。
空间局部性
概念：如果一个信息项被访问，那么与它相邻的信息项也很可能被访问。
应用：在缓存中存储连续的数据块，因为程序倾向于顺序访问内存。
高速缓存技术
原理：使用小而快速的存储器（缓存）来存储最近或频繁访问的数据，以减少对慢速主存储器的访问。
类型：指令缓存、数据缓存、统一缓存等。
虚拟内存的定义和特征
定义
虚拟内存是一种内存管理技术，它允许一个程序在逻辑上使用比实际物理内存更大的地址空间。
特征
地址空间分离：每个进程都有自己的虚拟地址空间，与物理内存分离。
动态内存分配：内存按需分配，不需要在程序启动时分配全部内存。
内存保护：防止一个进程访问另一个进程的内存空间。
内存映射：虚拟地址到物理地址的映射由操作系统和硬件（如内存管理单元MMU）管理。
如何实现虚拟内存技术
分页（Paging）
原理：将虚拟内存和物理内存划分为固定大小的页。
实现：操作系统维护页表，MMU负责将虚拟页映射到物理页框。
段页式（Segmented Paging）
原理：结合分段和分页，先将进程逻辑地址空间分段，再对每段进行分页。
实现：维护段表和页表，进行两级地址转换。
页面置换（Page Replacement）
算法：当物理内存不足以存放所有虚拟页时，使用页面置换算法（如LRU、FIFO）来决定哪个页被换出。
实现：操作系统负责选择页面置换策略，并在需要时执行页的换入和换出。
硬件支持
MMU：内存管理单元负责地址转换和内存保护。
磁盘存储：用作虚拟内存的后备存储，通常称为交换空间或分页文件。
2. 页面置换算法
OPT（最优页面置换算法，Optimal Page Replacement）
原理：替换掉最长时间内不会被访问的页面，这是一种理想化的算法，因为它需要未来的访问信息，实际上是不可实现的。
特征：没有页面错误，但仅用于理论上的性能比较。
FIFO（先进先出页面置换算法，First In, First Out）
原理：替换掉最先进驻内存的页面，即替换驻留时间最长的页面。
特征：实现简单，但可能会产生Belady异常（增加分配的帧数反而增加了缺页中断的次数）。
LRU（最近最少使用页面置换算法，Least Recently Used）
原理：替换掉最近最少被访问的页面。
特征：性能接近OPT，但需要额外的硬件或软件来记录每个页面的访问历史。
CLOCK（时钟页面置换算法）
原理：使用一个简单的时钟指针在页面的引用位（使用位）和修改位（脏位）之间循环，选择下一个符合条件的页面进行替换。
特征：简单高效，不需要记录大量的历史信息。
改进型的时钟置换算法
原理：在基本CLOCK算法的基础上进行改进，以更好地利用页面的访问模式。
几种改进：
第二次机会算法：在CLOCK算法的基础上，给每个页面一个额外的引用位，如果一个页面被访问过，即使它的引用位是0，也给予第二次机会。
增强时钟算法：考虑页面的修改位，优先替换未被修改的页面，以减少磁盘写操作。
扫描算法：结合了FIFO和CLOCK算法的特点，分为两个方向扫描，一个是FIFO方向，另一个是逆FIFO方向。
3.页面分配策略
驻留集（Resident Set）
定义：驻留集是指在任何给定时间点，进程在物理内存中占用的页框集合。
作用：决定了进程能够访问的内存大小，以及可能发生的缺页中断的频率。
页面分配、置换策略
固定分配局部置换（Fixed Allocation with Local Replacement）
原理：为每个进程分配固定数量的页框，当需要更多页框时，只能在进程的驻留集中进行页面置换。
特点：简单，但可能导致内存浪费或频繁的页面置换。
可变分配全局置换（Variable Allocation with Global Replacement）
原理：根据系统当前的内存使用情况，动态地为进程分配页框，当需要更多页框时，可以在整个物理内存中进行页面置换。
特点：提高了内存利用率，但可能增加管理复杂度。
可变分配局部置换（Variable Allocation with Local Replacement）
原理：结合了固定分配和可变分配的特点，为进程分配一个最小驻留集，并根据需要动态增加页框，但页面置换仍然在进程的驻留集中进行。
特点：平衡了内存利用率和置换开销。
调入页面的时机
需求调页（Demand Paging）：仅在进程访问一个不在物理内存中的页面时，才将其调入内存。
预调页（Prepaging）：在进程实际需要之前，就预先将一些页面调入内存。
从何处调页
磁盘上的交换区（Swap Space）：通常在磁盘上划分一个区域用于存储被置换出去的页面。
文件系统：对于共享库和可执行文件，页面可以直接从文件系统中读取。
抖动现象（Thrashing）
定义：当系统花费大量时间在页面置换上，而实际的工作进展很少时，系统处于抖动状态。
原因：进程的驻留集太小，导致频繁的缺页中断和页面置换。
工作集（Working Set）
定义：工作集是指在一定时间内，进程访问的页面的集合。
作用：用于确定进程的驻留集大小，以减少缺页中断和抖动现象。
4.内存映射文件
特性
进程可以使用系统调用，请求操作系统将文件映射到进程的虚拟地址空间。
以访问内存的方式读写文件
进程关闭文件时，操作系统负责将文件数据写回磁盘，并解除内存映射。
多个进程可以映射同一个文件，方便共享。
优点：
程序员编程更简单，已建立映射的文件，只需按访问内存的方式读写即可。
文件数据的读入/写出完全由操作系统负责，I/O效率可以由操作系统负责优化。
Last updated