哈工大李治军老师OS课程笔记（4）——内存管理

一 内存使用与分段（实验六）

内存是如何用起来的？
内存使用：将程序放在内存中，PC指向开始地址

重定位：修改程序中的地址（是相对地址）

什么时候完成重定位？
编译时加基址
缺点：编译的时候就得知道哪段内存是空闲的，但是在实际的系统中很难做到，比如编译的时候1000处是空闲的，但是执行的时候就不一定了。
载入时加基址更灵活

• 编译时重定位的程序只能放在内存固定位置
• 载入时重定位的程序一旦载入内存就不能动了

编译是将源代码转换为可执行代码的过程。它包括以下步骤：
1.词法分析：将源代码分解为词法单元（tokens），如标识符、关键字、运算符等。
2.语法分析：根据语法规则将词法单元组织成语法树（syntax tree）。
3.语义分析：检查语法树的语义正确性，进行类型检查和语义规则验证。
4.中间代码生成：生成中间表示形式，如抽象语法树（AST）或中间代码。
5.优化：对中间代码进行优化，提高程序的性能和效率。
6.目标代码生成：将优化后的中间代码转换为目标机器的汇编代码或机器代码。
编译器负责执行以上步骤，将源代码转换为可执行代码或可加载的目标文件。编译产生的目标文件可能包含可执行代码、库函数、符号表等。

加载是将目标文件或可执行代码加载到内存中并执行的过程。它包括以下步骤：
1.内存分配：为程序分配足够的内存空间，包括代码段、数据段、堆和栈等。
2.符号解析：解析目标文件中的符号表，建立符号与内存地址之间的关联。
3.重定位：如果目标文件中存在地址引用，进行地址修正，将相对地址转换为实际的内存地址。
4.加载到内存：将目标文件的代码和数据加载到相应的内存段中。
5.初始化：执行程序的初始化代码，如全局变量的初始化、运行时库的初始化等。
6.执行：跳转到程序的入口点，开始执行程序的指令。
加载器（Loader）负责执行以上步骤，将目标文件加载到内存中并启动程序的执行

重定位最合适的时机——运行时重定位
进程再执行过程中会发生变化，不一定每次执行都放在同一块内存空间，程序的基址存放在PCB中。当一次运行时程序被放在内存1000的位置，PCB中的base为1000，换出再换入到地址2000的地方，PCB中的base为2000。执行指令时第一步 先从PCB中取出这个基地址。基地址加上程序中的逻辑地址就得到了这条指令真正的物理地址。

找到空闲内存，将这段空闲程序基地址放到PCB中，然后将程序放入空闲内存

分段

在编译过程中，源代码会经过一系列的编译器处理，其中的一个重要步骤是将源代码转换为可执行的机器代码。这个过程中，编译器会将程序按照功能或作用划分为不同的段，通常包括代码段、数据段和堆栈段。

1.代码段（Code Segment）：
代码段包含程序的指令（机器代码），用于执行程序的操作。在程序执行时，代码段会被加载到内存中，并按照指令的顺序依次执行。
2.数据段（Data Segment）：
数据段存储程序的静态变量和全局变量等数据。这些变量在程序运行过程中会保持不变，存储在数据段中的数据在整个程序执行期间都是可访问的。
3.堆栈段（Stack Segment）：
堆栈段用于存储程序执行期间的局部变量、函数调用信息和函数返回地址等。每当程序调用函数或进入一个新的作用域时，相关的数据会被压入堆栈中，当函数返回或作用域结束时，相关数据会被弹出。堆栈的管理由程序在运行时负责

分段符合用户观点：用户可独立考虑每个段（分治）

操作系统对应的段表就是GDT表，每个进程对应的段表是LDT表。段表形式如下图所示：

把程序分成多个段，在内存中找到空闲的地方，把段放进去，记录这个段在内存中的基址放入LDT表，把LDT表中赋给PCB，将PC指针设为程序初值，每次取值执行都去查LDT表，根据LDT表找到该条指令的基址，再加上程序中的偏移地址获得该条指令的物理地址。
内存使用三部走：分段+找空闲分区+映射表

二、内存分区与分页

1、内存分区

一个程序分成多个段（编译干的事儿），在内存中找到一个空闲区域（算法数据结构），通过磁盘读写把程序载入进来（设备驱动），建立映射表和PCB关联（进程管理）

如何找出一段空闲的分区？内存怎么分割？
可变分区的管理过程

首先适配（350,150）速度快 O(1)
最佳适配（200,50） 碎片多
最差适配（350,150）O(n)

2、内存分页

物理内存要使用分页

内存碎片太太多，将空闲分区合并，这个时候需要移动内存，这个操作叫内存紧缩，在这个过程中，计算机中其他进程也无法运行。内存紧缩需要花费大量的时间，如果复制速度1M/1秒，则1G内存的紧缩时间为1000秒。内存紧缩管理内存碎片太消耗时间了，在实际情况中不可行。

让面包没有谁都不想要的碎末——将面包分成片，类比可以将内存分成页。

内存分页
针对每个段的内存请求，系统一页一页的分配给这给段。

将每个段分页，并编页号，将每页放入空闲的页面中，并将页框号与段页号的对应关系放入页表中，当CPU取值执行时，根据页表和程序中的偏移地址找到该条指令的物理地址。

通常，计算机存储中的 “K” 表示 1024，即 1K = 1024 字节。因此，12K 表示 12 * 1024 字节，即 12,288 字节。接下来，将 12,288 转换为十六进制。12,288 的十六进制表示为 0x3000。因此，将 12K 转换为十六进制为 0x3000。

三、多级页表与快表

32位地址空间+4K页面+页号必须连续 => 2^20个页表项 => 大页表占用内存，造成浪费。

如果用一个变量标识该页有没有使用，用到的逻辑页才有页表项，页表中的页号不连续，就需要比较、查找、折半，降低效率。如果页表连续，只需要一次查找就能找到需要的页。

既要连续又要让页表占用内存少，怎么办？

多级页表 页目录表+页表

多级页表提高了空间效率，使用快表提高效率

四、 段页结合的内存管理

段页同时存在：段面向用户/页面向硬件。虚拟内存是一块地址空间
页表是一个数据结构，用于存储虚拟地址和物理地址之间的映射关系。页表中的每一项存储了一个虚拟页号到物理页框号的映射。

虚拟内存是计算机操作系统中的一种技术，它提供了一种抽象的、相对较大的内存空间，使得程序可以访问比物理内存更大的地址空间。虚拟内存的主要目的是扩展计算机系统的内存容量，使得运行大型程序和处理大量数据时更加高效。它通过将物理内存和硬盘上的存储空间结合起来，创建一个逻辑上连续且更大的地址空间供程序使用。

在虚拟内存的机制下，每个程序都被分配了一块连续的虚拟内存空间，该空间被划分为固定大小的块，称为页面（或页）。物理内存也被划分为与页面大小相同的块，称为物理页面（或页框）。当程序需要访问虚拟内存中的某个页面时，操作系统会将该页面从硬盘加载到物理内存中的一个空闲页框中，并建立虚拟内存与物理内存之间的映射关系。虚拟内存的使用带来了以下几个主要的好处：
1.内存扩展：虚拟内存使得程序能够使用比实际物理内存更大的地址空间，从而能够运行更大的程序或处理更多的数据。
2.内存隔离：每个程序都有自己独立的虚拟内存空间，相互之间不会干扰。这提供了更好的安全性和稳定性，一个程序的崩溃不会影响其他程序的运行。
3.虚拟内存管理：操作系统负责管理虚拟内存和物理内存之间的映射关系，根据程序的需求进行页面的加载和卸载。它可以将不常用的页面置换（交换）到硬盘上，从而释放物理内存供其他程序使用。
4.内存保护：虚拟内存允许操作系统为每个页面设置访问权限，例如只读、读写、执行等。这样可以防止程序对其它程序或操作系统的内存空间进行非法访问。

地址翻译

段页式内存下程序如何载入内存：

• 找到空闲段
• 把段程序“假装”放在虚拟内存上，建立段表
• 在物理内存中找空闲页
• 建立页表
• 利用重定位使用内存

五、 内存换出换出

1、内存换入——请求调页

没有换入换出，虚拟内存实现不了。
用换入换出实现“大内存”

假设虚拟内存有4G大小，但是对应的实际物理内存只有1G大小，如何给用户大内存的感觉呢？

将虚拟内存比作仓库，物理内存比作门店
缺页引起内存的换入

2、内存换出

算法评价准则：缺页次数

（1）FIFO

（2）MIN算法

选择最远将使用的页淘汰

（3）LRU页面置换

用过去的历史预测将来。LRU：选最近最长一段时间没有使用的页淘汰（最近最少使用）。
实现方法

• 时间戳，每页维护一个时间戳，选具有最小时间戳页淘汰。
  缺点：每次地址访问都需要修改时间戳，需要维护一个全局的时钟，找到最小值，实现代价较大。
• 维护一个页码栈
  

每次地址访问都需要修改栈（修改10次左右栈指针），实现代价大。

LRU近似实现 ——clock算法