一张思维导图看操作系统【持续迭代】

Tinggeng included in OS

2022-07-17 1109 words 6 minutes views

Contents

概述

总结自己的操作系统的知识，按照编码 -> 运行，画了一张图，xmind 导出的图比较大，目前这部分的内容还比较少，后续持续更新，迭代这部分的内容。

下面是一些常见的知识,将会慢慢补充进思维导图内

linux 整体结构图

makelinux：makelinux

解释器 & 编译器 & JIT & AOT

JIT(Just In Time)和 AOT(Ahead Of Time)是两种不同的编译方式:

JIT:

编译时,将源代码编译成字节码(bytecode),运行时再将字节码编译成机器码。
优点是运行时可以进行更多优化,生成更高质量的机器码。
缺点是编译时需要额外的编译步骤,会增加程序启动时间。
第一次运行时编译时间较长,后续运行时间短。运行时性能较AOT略差。

AOT:

编译时,将源代码直接编译成机器码。
优点是编译只有一次,程序启动更快。
编译器在程序运行前完成编译,生成机器代码。运行时直接执行机器代码。
编译时间较长,运行时性能好。
改动源代码需要重新编译。
缺点是编译时难以进行复杂的优化,生成的机器码质量可能较低。
典型的AOT编译语言有C、C++等。

总结:

JIT 的运行性能更高,但启动时间长。适合长时间运行的程序。
AOT 的启动时间短,但运行性能可能略低。适合启动频繁的程序。
在实际使用中,也可以二者结合,采用 AOT 先编译成机器码,再运行时由 JIT 进一步优化,以兼顾启动时间和运行性能。许多语言(如 Java、C#)的编译器都支持这两种模式。

![[Pasted image 20230407143623.png]]

解释器：Java源程序编译成字节码，然后由运行环境对字节码解释执行，提供解释功能的 JVM 组件为解释器。它能执行 JVM 规范的字节码，执行方式是一遍翻译一遍执行，所以效率低，但是简单并易于实现。主要实现是在 Interpreter 模块。

![[Pasted image 20230407143647.png]] 即时编译器：能够将运行时的热点代码，编译成运行效率高的及时代码。判断一段代码是不是热点代码，是不是需要触发JIT编译，这样的行为称为：热点探测（Hot Spot Detection），有几种主流的探测方式：

基于计数器的热点探测（Counter Based Hot Spot Detection）：虚拟机会为每个方法（或每个代码块）建立计数器，统计执行次数，如果超过阀值那么就是热点代码。缺点是维护计数器开销。
基于采样的热点探测（Sample Based Hot Spot Detection）：虚拟机会周期性检查各个线程的栈顶，如果某个方法经常出现在栈顶，那么就是热点代码。缺点是不精确。
基于踪迹的热点探测（Trace Based Hot Spot Detection）：Dalvik中的JIT编译器使用这种方式

JIT 是可以回退到解释器执行的

inlining 内联(最关键的优化手段) inlining 指在编译时，识别 call site (持有 method handle 的对象) 的目标方法，将其方法体加入当前方法的编译范围，并将其结果替换掉原 call site，比如 getter 和 setter 就会优化为一条访问内存的指令。

通过谨慎地使用 AOT 编译代码加快应用程序启动，因为虽然这种代码通常比 JIT 编译代码慢，但是却比解释代码快很多倍。此外，因为加载和绑定AOT 编译代码的时间通常比检测和动态编译一个重要方法的时间少，所以能够在程序执行的早期达到那样的性能。类似地，交互式应用程序可以很快地从本地代码中获益，无需使用引起较差响应能力的动态编译。

AOT的核心原理是:编译时将源代码编译成机器代码,然后在运行时直接执行机器代码。具体来说,主要分为以下几个步骤:

编译:这个过程通常较慢,开发者编写的源代码会被编译器编译成机器代码,并链接成完整的可执行文件。
运行:此时运行可执行文件,直接执行机器代码,不需要额外的编译步骤,所以运行速度很快。
优化:编译器可以充分利用编译期的时间来对机器代码进行优化,如删除冗余代码、循环展开等,这也是AOT性能好的原因之一。
缓存:由于机器代码是预先编译好的,所以编译的中间结果(如AST)可以被缓存下来重复使用,这也提高了性能。
静态分析:编译器可以在编译期对源代码进行静态分析,发现潜在的bug或安全隐患,这是AOT的另一大优势。

所以AOT的关键就是将程序的编译过程前置到运行之前,生成机器代码,这样运行时只需要简单执行机器代码即可,省去编译的开销,这也是AOT能达到运行性能较高的原因。但也因此,AOT语言在开发调试阶段的体验稍差,因为每次修改源代码都需要重新编译。总体来说,AOT通过提前编译,牺牲部分编译的开销和开发体验,换取运行期的高性能表现。这也使其非常适合在生产环境部署。

JIT的核心原理是:编译器在程序运行时对源代码进行编译,生成机器代码,然后直接执行。具体来说,主要分为以下几个步骤:

解释:程序首次运行时,解释器逐行解释源代码,并执行。这一步编译开销较大,运行较慢。
profiling:解释器会检测程序的热点代码(频繁执行的代码),并选择优化它们。
编译:解释器会将热点代码编译成机器代码,然后缓存起来。
运行:第二次运行热点代码时,直接执行缓存的机器代码,省去解释的开销,运行速度明显提高。
优化:JIT编译器会对热点代码进行进一步的优化,如内联扩展、去虚拟化等,提高性能。
缓存分享:不同运行实例之间可以共享JIT缓存,减少编译工作,这也是JIT的优化手段之一。

所以JIT的关键是将编译过程推迟到程序运行时,并只编译热点代码,其他代码继续由解释器解释。这使得JIT在第一次运行时有一定开销,但可以达到较好的运行性能,且编译结果可以在多次运行间重复使用。 JIT的优点是开发体验好,修改代码后无需重新编译,直接运行即可。但运行时会有一定的编译开销,性能也比AOT略差。所以,JIT更适用于开发调试阶段,以及对运行性能要求不高的场景。总之,JIT通过将编译过程推迟到程序运行时,在保证开发体验的同时,通过热点代码编译和优化,获得还可以的运行性能,这就是JIT的核心原理。

Android 中使用的是 JIT 还是 AOT ？

Android使用的启动方式是把JIT和AOT混合使用:

JIT部分:
- Android程序通常使用Java语言编写,运行在Dalvik/ART虚拟机上。
- Dalvik/ART会在程序第一次运行时将Java字节码解释执行(解释器方式)。
- 然后它会检测热点代码,并利用JIT编译器将热点代码编译成机器码缓存并执行。
- 这部分属于典型的JIT方式。

1. AOT部分:
- 从Android 7.0 开始,Google 推出了一种新的 AOT 编译模式，一般称为 *profile-guided *。
- 开发者可以让ART AOT编译器在安装应用时提前编译应用的Java字节码为机器码。
- 然后在每次运行应用时,直接执行预编译好的机器码,而不是先解释Java字节码。
- 这部分属于典型的AOT方式,可以减少运行时的性能开销,提高应用启动速度。
1. 混合使用:
- 在Android的大部分时间里,仍然是采用JIT方式运行Java字节码和机器码的混合方式。
- JIT方式适合开发调试,AOT方式适合生产环境APP。
- 从Android 7.0开始,开发者可以根据需要选择JIT,AOT或混合的方式来启动自己的应用。

所以,总体来说,虽然Android运行环境本质上是一种JIT虚拟机,但是从Android 7.0开始,Google为了追求更高的运行性能,允许开发者选择AOT方式启动APP。这使得Android可以很好的适用JIT和AOT各自的优势,是一种非常灵活的设计。所以答案是:Android既使用JIT,也使用AOT,并可以根据需要选择两种方式或混合使用。

动态链接、静态链接

动态链接和静态链接都是程序中调用库文件的方式,但有以下主要区别:

链接时间:
- 静态链接:在编译时将库文件链接到可执行文件中,产生完整的可执行文件。
- 动态链接:在运行时将库文件链接到可执行文件中。
空间占用:
- 静态链接:库文件代码被复制到每个可执行文件中,空间占用较大。
- 动态链接:库文件只有一份,被多个可执行文件共享,空间占用较小。
依赖性:
- 静态链接:可执行文件不依赖于库文件,可以独立运行。
- 动态链接:可执行文件依赖于库文件,需将库文件与可执行文件放在一起才能运行。
版本问题:
- 静态链接:可执行文件使用的是链接时库文件的代码,Even if库文件更新,可执行文件还是使用原来的代码。
- 动态链接:可执行文件使用的都是最新的库文件代码,如果库文件更新,可执行文件自动使用最新代码。

总的来说,

静态链接产生的可执行文件更独立和稳定,但空间占用更大;
动态链接产生的可执行文件更灵活和节省空间,但依赖性更强。
- 动态链接还可以进一步细分为运行时链接和装载时链接,这是实现层面的细节差异。
- 本质上,它们都是动态链接,在程序运行期将库文件的代码装入进程地址空间。
大部分情况下,我们选择动态链接来利用库文件。

Linux的软链接和硬链接吗？

Linux链接分两种，一种被称为硬链接（Hard Link），另一种被称为符号链接（Symbolic Link）。默认情况下，ln命令产生硬链接。

硬连接

硬连接指通过索引节点来进行连接。在Linux的文件系统中，保存在磁盘分区中的文件不管是什么类型都给它分配一个编号，称为索引节点号(Inode Index)。在Linux中，多个文件名指向同一索引节点是存在的。一般这种连接就是硬连接。硬连接的作用是允许一个文件拥有多个有效路径名，这样用户就可以建立硬连接到重要文件，以防止“误删”的功能。其原因如上所述，因为对应该目录的索引节点有一个以上的连接。只删除一个连接并不影响索引节点本身和其它的连接，只有当最后一个连接被删除后，文件的数据块及目录的连接才会被释放。也就是说，文件真正删除的条件是与之相关的所有硬连接文件均被删除。

软连接

另外一种连接称之为符号连接（Symbolic Link），也叫软连接。软链接文件有类似于Windows的快捷方式。它实际上是一个特殊的文件。在符号连接中，文件实际上是一个文本文件，其中包含的有另一文件的位置信息。

1
2
3
4
5


## 创建软链接
ln -s file1 link1 

## 创建硬链接
ln file1 link2

内存管理

参考链接1

Linux 的内存管理可以简述如下:

Linux采用分页式内存管理,将内存分割成大小相等的块,称为页(page)。每个页的大小通常是4KB。
Linux内存管理有两种方式:交换区(swap)和直接存取(direct access)。
- 当物理内存页不足时,操作系统会将暂时不使用的页交换出去,这种方式称为交换区管理。
- 如果物理内存足够,操作系统会将进程映射到物理内存,这种方式称为直接存取。
Linux采用Demand Paging机制,只有当进程真正访问某个虚拟内存页时,才会将其映射到物理内存。如果此时物理内存不足,会选择一个未使用的页交换出去。
Linux内存管理还采用LRU算法来选择交换出的页。LRU算法按照页的最近使用情况来决定哪些页应该被交换出去。最近最少使用的页会被先选中交换出物理内存。
Fork系统调用可以 COPY ON WRITE技术来避免重复映射物理内存页。只有当父进程和子进程中有一个要修改某共享页时,才会真正复制一份。这可以节省物理内存的使用。
Linux提供匿名映射和文件映射两种内存映射方式。匿名映射不和文件关联,文件映射则和文件关联。
Linux还提供共享内存和匿名管道等IPC机制,以实现进程间的内存共享。

Linux 提供两种内存映射方式:

匿名映射(anonymous mapping): 不和任何文件关联,仅映射到虚拟内存地址空间。使用 mmap() 系统调用实现,指定映射长度和可读写权限,操作系统会返回一个虚拟内存起始地址。这块内存区域初始化为0。
文件映射(file mapping): 和打开的文件关联,文件中的数据会映射到虚拟内存地址空间。也使用 mmap() 系统调用实现,需要指定想要映射的文件描述符和长度等信息。文件的数据会直接映射到内存,读取内存就相当于读取文件。这两种映射方式的主要区别是:

匿名映射初始化为0,文件映射初始化为文件的内容。
文件映射会与文件同步,对映射区的修改会写入文件,文件修改也会同步到映射区。匿名映射没有这种同步效果。
删除文件描述符不会对文件映射产生影响,它会一直到 munmap() 系统调用释放映射才解除映射。匿名映射关闭最后一个对其的引用时则会释放。
文件映射是共享的,父子进程可以共享同一映射。匿名映射默认是私有的,要启用 MAP_SHARED 标志来共享。

这些内存映射方式提供了一种高效的 I/O 方式,用户空间应用可以像访问内存一样访问文件,这加快了文件访问速度。同时也带来方便的进程间通信方式。总之,内存映射是Linux下一个强大而高效的 IPC 机制。

匿名映射 & 命名映射

mmap

它可以带来的好处有：

减少系统调用。我们只需要一次 mmap() 系统调用，后续所有的调用像操作内存一样，而不会出现大量的 read/write 系统调用。
减少数据拷贝。普通的 read() 调用，数据需要经过两次拷贝；而 mmap 只需要从磁盘拷贝一次就可以了，并且由于做过内存映射，也不需要再拷贝回用户空间。
可靠性高。mmap 把数据写入页缓存后，跟缓存 I/O 的延迟写机制一样，可以依靠内核线程定期写回磁盘。但是需要提的是，mmap 在内核崩溃、突然断电的情况下也一样有可能引起内容丢失，当然我们也可以使用 msync 来强制同步写。

它也存在一些缺点：

虚拟内存增大。mmap 会导致虚拟内存增大，我们的 APK、Dex、so 都是通过 mmap 读取。而目前大部分的应用还没支持 64 位，除去内核使用的地址空间，一般我们可以使用的虚拟内存空间只有 3GB 左右。如果 mmap 一个 1GB 的文件，应用很容易会出现虚拟内存不足所导致的 OOM。
磁盘延迟。mmap 通过缺页中断向磁盘发起真正的磁盘 I/O，所以如果我们当前的问题是在于磁盘 I/O 的高延迟，那么用 mmap() 消除小小的系统调用开销是杯水车薪的。启动优化中讲到的类重排技术，就是将 Dex 中的类按照启动顺序重新排列，主要为了减少缺页中断造成的磁盘 I/O 延迟。

适用场景 mmap 比较适合于对同一块区域频繁读写的情况，推荐也使用线程来操作。用户日志、数据上报都满足这种场景，另外需要跨进程同步的时候，mmap 也是一个不错的选择。Android 跨进程通信有自己独有的 Binder 机制，它内部也是使用 mmap 实现。

对于大文件，大的 value ，是不合适的，如何解决大文件读写的问题，参考文章 在高并发的场景下，针对大文件的传输的方式，应该使用「异步 I/O 」来替代零拷贝技术。
针对大文件的传输，不应该使用 PageCache，也就是说不应该使用零拷贝技术，因为可能由于 PageCache 被大文件占据，而导致「热点」小文件无法利用到 PageCache，这样在高并发的环境下，会带来严重的性能问题。

我们要根据文件的大小来使用不同的方式：

传输大文件的时候，使用「异步 I/O + 直接 I/O」；
传输小文件的时候，则使用「零拷贝技术」；

mmap 的应用 - 日志库

由于内存Cache的存在，在写入数据的过程中一旦发生意外（Crash、后台被系统杀死，等），都可能会发生数据丢失的情况。而如果将写操作设计成同步的，数据丢失的情况会有所改善，但写操作的耗时会大大提升。mmap 的引入恰到好处的在这两者之间找到了一个平衡。mmap 对文件的读取操作跨过了页缓存，减少了数据的拷贝次数，用内存读写取代I/O读写，提高了文件读取效率；对 mmap 内存的写操作，会直接进入系统page-cache；msync调用负责把脏的page-cache持久化到硬盘。当然对发生系统级错误和设备异常导致系统挂掉的情况，mmap 也是保证不了数据完整性的。

这里需要特别说明一下：MMKV 实现的本质上跟前面讨论的KV方案是没有区别的，其最大的改进是利用 mmap 来代替 File 和 Database 的操作，利用 mmap I/O 操作的优势对数据丢失问题进行改善。但由于“内存-文件”两级缓存的存在，MMKV 也是无法彻底解决数据丢失问题的。当然对于终端设备的场景来看，这种丢失在很大程度上是可以忽略的。

微信团队在封装 xlog 和 mmap 时采用了CPP代码来实现，主要是为了做到 Android 和 iOS 端的通用。实际上如果不考虑跨平台，则可以考虑使用 Java NIO 中的 FileChannel 或者 Android 中的 MemoryFile 代替。 FileChannel 底层其实通过 mmap 实现的。而 MemoryFile 则是 Android 中匿名共享内存在 Java 层的接口，至于 Android 匿名共享内存底层实现也利用了mmap。所以，FileChannel 和 MemoryFile 本质上与直接调用 mmap 是一样的。利用这些接口也可以降低大部分 Android 程序员的开发和维护成本，毕竟大家对 Java 相对更为熟悉。下面是在 KV 设计中另一种 Key 的设计方案：

我们在数据存储时，以32位的 Int 作为作为 Key ，其中：

低位 24 位来定义 Key 的长度；
最高位，第 32 位表示 Key 是否有效：为 1 时表示 Key 无效，读取时跳过
第 31 位表示是否加密：为 1 时表示未加密，不需要解密处理；
第 30 位表示是否需要编码：为 1 时表示保存明文，不进行转码处理；
中间 25 - 29 位预留，以后扩展用

这样设计Key的优点：

在加载的时候只根据 Key 就可以判断数据是否有效，无效数据不需要加载到内存；MMKV 则是依靠相同 Key 在 put 到 map 中时先后顺序的覆盖实现的，对于无效数据需要根据 Key 进一步得到 Value，判断 Value 的长度是否为 0 。
可以一定程度实现空间重用，当更新后的 Value 长度不超过旧值的长度时，可以直接复用原来的空间，在 Value 长度超过旧值时将 Key 的有效位置 1 ，然后再在尾部 append Key-Value即可。当然这里只是“一定程度”上改善，要想进一步做到空间重用，还可以考虑：
- 对字符串等经常变长的 Value 在第一次写入的时候就留有一定的空间冗余度；
- 通过一个内存的堆栈对无效空间进行管理，甚至你可以模仿内存的分配策略做的更加完善

因此，这里如何做是一个“度”的问题，而这个“度”的把握则取决于对设备和产品的理解。对微信来说，他们的理解是 append 就够了，个人理解是可以做一定程度（“简单”）复用策略的，通过复用减缓到达空间上限的时间，因为每次加载时 Key 的去重以及回写都是有一定的性能开销的。这样设计 Key 相对更加灵活，可以对数据加密、编码等根据需要搭配，做到不同形式数据的混存

直接 IO 与非直接 IO

我们都知道磁盘 I/O 是非常慢的，所以 Linux 内核为了减少磁盘 I/O 次数，在系统调用后，会把用户数据拷贝到内核中缓存起来，这个内核缓存空间也就是「页缓存」，只有当缓存满足某些条件的时候，才发起磁盘 I/O 的请求。

那么，根据是「否利用操作系统的缓存」，可以把文件 I/O 分为直接 I/O 与非直接 I/O：

直接 I/O，不会发生内核缓存和用户程序之间数据复制，而是直接经过文件系统访问磁盘。
非直接 I/O，读操作时，数据从内核缓存中拷贝给用户程序，写操作时，数据从用户程序拷贝给内核缓存，再由内核决定什么时候写入数据到磁盘。

如果你在使用文件操作类的系统调用函数时，指定了 O_DIRECT 标志，则表示使用直接 I/O。如果没有设置过，默认使用的是非直接 I/O。

如果用了非直接 I/O 进行写数据操作，内核什么情况下才会把缓存数据写入到磁盘 以下几种场景会触发内核缓存的数据写入磁盘：

在调用 write 的最后，当发现内核缓存的数据太多的时候，内核会把数据写到磁盘上；
用户主动调用 sync，内核缓存会刷到磁盘上；
当内存十分紧张，无法再分配页面时，也会把内核缓存的数据刷到磁盘上；
内核缓存的数据的缓存时间超过某个时间时，也会把数据刷到磁盘上；

阻塞与非阻塞 I/O VS 同步与异步 I/O

IO 整体分为两个过程

数据准备的过程；
数据从内核空间拷贝到用户进程缓冲区的过程；

阻塞 I/O 会阻塞在「过程 1 」和「过程 2」，而非阻塞 I/O 和基于非阻塞 I/O 的多路复用只会阻塞在「过程 2」，所以这三个都可以认为是同步 I/O。

异步 I/O 则不同，「过程 1 」和「过程 2 」都不会阻塞。

进程和线程

区别联系

进程和线程的主要差别在于它们是不同的操作系统资源管理方式。

进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，
而线程只是一个进程中的不同执行路径。
线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，
但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

简而言之,一个程序至少有一个进程,一个进程至少有一个线程。
线程的划分尺度小于进程，使得多线程程序的并发性高。
另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。
线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
【重要】从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。

进程的调度算法

先来先服务调度算法，（First Come First Severd, FCFS） 先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。 FCFS 对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。

最短作业优先（Shortest Job First, SJF）调度算法 优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。这显然对长作业不利，很容易造成一种极端现象。长作业一直得不到执行。

高响应比优先（Highest Response Ratio Next, HRRN）调度算法 主要是权衡了短作业和长作业。每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行，「响应比优先级」的计算公式：

时间片轮转（Round Robin, RR）调度算法。 每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。

如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；
如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

时间片的长度就是一个很关键的点：

如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；
如果设得太长又可能引起对短作业进程的响应时间变长；

通常时间片设为 20ms~50ms 通常是一个比较合理的折中值。

最高优先级（Highest Priority First，HPF）调度算法。

从就绪队列中选择最高优先级的进程进行运行。

进程的优先级可以分为，静态优先级或动态优先级：

静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

该算法也有两种处理优先级高的方法，非抢占式和抢占式：

非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

但是依然有缺点，可能会导致低优先级的进程永远不会运行。

多级反馈队列（Multilevel Feedback Queue）调度算法

「多级」表示有多个队列，每个队列都有一个优先级，队列按照优先级从高到低排列，同时优先级越高时间片越短。
「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；

工作流程

设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；

可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

死锁和死锁避免

死锁产生的原因有以下几个:

互斥条件:一个资源一次只能被一个进程使用；
请求和保持条件:一个进程因为获得了一个资源而阻塞时,仍然保持对其他资源的请求；
不可剥夺条件:进程已经获得的资源,不能被其他进程强行剥夺,直到该进程使用完毕为止；
循环等待条件:若干进程之间形成一种头尾相接的等待资源关系,造成循环等待。

避免死锁,主要是破坏4个必备条件即可，可以采取以下措施:

破坏互斥条件:不做
破坏请求和保持条件:进程在请求资源时,不保持对其他资源的请求。 Release所有资源后再请求其他资源。
破坏不可剥夺条件:允许进程在等待期间,被其他进程剥夺资源。但这可能影响运行正确性,不太可取。
破坏循环等待条件:按某种顺序获取多个资源,避免循环等待。如按资源标号顺序获取资源。
使用资源继承线程:让每个资源都只有一个线程可以获取,其他线程必须等待。此时多个线程竞争同一资源时不会发生死锁。
设置资源请求超时时间:如果在一定时间内不能获取资源,则放弃请求。避免一直等待下去。
减少对资源的请求数目:合理分配和调度资源,避免过多进程同时请求少量资源。

线程的状态以及转换

*进程的状态图

线程状态图

参考链接1

线程调度的原则，考虑的就是速度快，需要考量的因素如下

CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

Java 线程的状态，有六种

NEW
RUNNABLE
BLOCKED
WAITING
TIMED_WAITING
TERMINATED

经典的线程五态模型，有五种状态

创建
就绪
执行
阻塞
终止

Java 将五态模型中的

就绪和执行，都统一成 RUNNABLE，
将阻塞（即不可能得到 CPU 运行机会的状态）细分为了 BLOCKED、WAITING、TIMED_WAITING，这里我们不去评价好坏。

调用 jdk 的 Lock 接口中的 lock，如果获取不到锁，线程将挂起，此时线程的状态是什么呢？ 有多少同学觉得应该和 synchronized 获取不到锁的效果一样，是变成 BLOCKED 状态？不过如果你仔细看我上面的文章，有一句话提到了，jdk 中锁的实现，是基于 AQS 的，而 AQS 的底层，是用 park 和 unpark 来挂起和唤醒线程，所以应该是变为 WAITING 或 TIMED_WAITING 状态。

调用阻塞 IO 方法，线程变成什么状态？ 比如 socket 编程时，调用如 accept()，read() 这种阻塞方法时，线程处于什么状态呢？答案是处于 RUNNABLE 状态，但实际上这个线程是得不到运行权的，因为在操作系统层面处于阻塞态，需要等到 IO 就绪，才能变为就绪态。但是在 Java 层面，JVM 认为等待 IO 与等待 CPU 执行权，都是一样的。

重开线程

Java 中的线程是不可以重开的；

进程和线程内存地址空间的区别

进程的地址空间是私有的,互不共享。
线程共享进程的地址空间,可以访问进程内所有变量和资源。
不同进程的线程不能共享地址空间。

线程同步机制

锁(Lock)。锁是最基本的线程同步机制,它允许线程对共享资源的访问进行互斥,从而保证同一时间只有一个线程可以访问该资源。常见的锁有互斥锁、读写锁等。
条件变量(Condition Variable)。条件变量允许线程等待某个条件满足后再继续执行。它通常与锁一起使用,锁保证访问共享资源的互斥,条件变量允许等待某个条件。
信号量(Semaphore)。信号量是一个计数器,它允许多个线程访问一个资源,但是同一时间访问的线程数量不可以超过计数器的值。它主要用于控制对资源的访问数量。
事件(Event)。事件允许一个线程通知其他线程某个事件已经发生,当事件发生时,Those等待线程会被唤醒。它主要用于线程间的通信和同步。
屏障(Barrier)。屏障允许多个线程在某个点汇集,当某个数量的线程到达屏障点后,这些线程才会继续执行。它主要用于多个线程同步执行。
自旋锁(Spinlock)。自旋锁是一种忙等待的锁,获取锁的线程会循环检测锁的状态,而不是睡眠,这可以减少线程上下文切换的开销,但是会占用更多的CPU资源。它主要用于同步对共享资源的访问。

所以总体来说,线程同步机制为我们提供了控制多个线程对共享资源访问的工具,保证数据的一致性和正确性。

同步机制中的锁和信号量的区别是什么？ 锁和信号量都是用于线程同步的机制,但是它们之间有以下主要区别:

锁是一种互斥机制,它允许同一时间只有一个线程访问共享资源。信号量是一种计数器,它允许多个线程访问共享资源,但是访问的线程数量不可以超过信号量的计数值。
锁通常只有两个状态:锁定和未锁定。信号量的计数器可以是任意非负整数。
想要访问共享资源的线程首先要获取锁,获取后该线程独占该资源,其他线程无法访问。想要访问共享资源的线程首先要获取信号量,获取将信号量的计数器减1,释放会让计数器加1,只要计数器的值大于0,线程就可以访问资源。
锁由调用 lock() 方法获取,调用 unlock() 方法释放。信号量由调用 acquire() 方法获取,调用 release() 方法释放。
锁可以用于同步任何类型的资源。信号量主要用于控制对资源的访问数量,通常用于实现资源池等。
锁的实现通常更轻量级,性能开销较小。信号量的实现相对复杂一些,性能开销较大。

所以总体来说,虽然锁和信号量都是用于线程同步的机制,但是锁是一种互斥的同步方式,而信号量是一种控制访问数量的同步机制。根据不同的需求,可以选择使用锁或者信号量来实现线程同步。

读写锁的原理

读写锁是操作系统中用于保护共享资源的一种锁机制。它允许多个读线程同时访问一个资源,但在写线程访问时会阻塞所有读线程和其他写线程。读写锁的主要原理是:

维护一个读计数器和一个写标志。读计数器记录当前有多少个读线程正在访问资源,写标志表示是否有写线程正在访问资源。
当一个读线程请求访问资源时,如果写标志是False,则读计数器加1,并允许读线程访问资源。如果写标志是True,则读线程等待。
当一个写线程请求访问资源时,如果读计数器和写标志都是False,则将写标志设置为True,并允许写线程访问资源。如果读计数器不为0或写标志为True,则写线程等待。
当一个读线程退出时,将读计数器减1。当写线程退出时,将写标志设置为False。
只有当读计数器和写标志都是False时,才允许下一个待命的写线程访问资源。

这样就可以实现多个读线程并发访问,而写线程互斥访问的效果。这样可以最大限度地提高资源的并发访问效率。这就是读写锁的基本原理。读写锁是相比互斥锁更细粒度的锁机制,在许多场景下可以实现更高的并发效率,所以在操作系统和许多程序中得到广泛应用。

Java 中的读写锁

JUC 中有 ReentrantReadWriteLock 和 StampedLock 这两个类，都是读写锁。区别在于 StampedLock 是读乐观的锁。

原子操作原理

https://zhuanlan.zhihu.com/p/33445834

从用户角度，可以用原子操作来替换重量级的锁同步，从而提高程序性能。
底层实现角度，原子操作可以用于构建各种更重量级的同步操作，比如锁或屏障之类的。

原子操作的原理是利用CPU的原子指令来确保操作的原子性。通常有两种方式:

硬件支持的原子指令,如CMPXCHG指令。这些指令本身就是原子的,可以直接实现原子操作。
锁定总线,使其他CPU无法访问共享内存。这种方式会临时锁定系统总线,使当前CPU独占总线,其他CPU无法访问内存。从而确保操作的原子性。这通常是通过获取一个锁来实现的。但这个方式的性能较低,现代CPU一般不采用这种方式。

原子操作的四个要素:

原子性:操作必须是不可中断的,要么全部完成,要么全部不完成,不会结束在中间某个状态。
可见性:当一个线程修改了共享数据的值,其他线程可以立即得知这个修改。
有序性:代码执行的顺序与程序顺序相同。
互斥性:在任意时刻,只能有一个线程修改共享数据。

常见的实现方式：

CAS(Compare And Swap)指令是最常用的实现原子操作的指令,它可以比较内存中一个位置的值,如果相等则更新为新值,否则不做任何操作。CAS是CPU提供的原子指令,可以直接实现原子操作。
许多CPU提供的原子指令,如xchg指令、xadd指令,这些都可以实现简单的原子操作。
锁是实现原子操作的一种重要方式。对某个锁对象上锁,执行一系列操作,然后释放锁,这整个过程是其他线程不可分割的,可以保证原子性。这需要使用互斥锁等同步原语。
有时候需要借助操作系统的帮助。例如,可以使用临界区(critical section)的方式,让操作系统在进入和退出临界区时禁止中断或者调度,从而实现原子操作。

实现原子操作有软硬件多种手段,但本质上都是利用CPU的原子指令或锁总线的方式来确保一系列操作的原子性

CAS 为什么可以保证原子性？

CAS是CPU的原子指令,不会被编译器优化或重排序。CPU会确保CAS整个操作过程不被中断,要么全部完成,要么全部不完成,不会中间被中断导致只完成一半。这就保证了操作的原子性。
CAS操作包含三个步骤:读取内存值A,比较A与预期值B,如果相等则写入新值C。这三个步骤是连续的,不会被其他线程的操作插入或重排序。所以从其他线程的视角来看,这三个步骤要么全部完成,要么都不完成,这也确保了原子性。
CAS操作在多处理器下需要锁总线,使当前CPU独占内存总线,其他CPU无法访问内存。这可以防止多个CPU同时执行CAS操作,导致某个CPU只完成了部分步骤就被中断,破坏原子性。锁总线可以确保任意时刻只有一个CPU可以执行CAS指令。
CAS保证了操作的互斥性,在任意时刻只能有一个CPU成功执行CAS指令,其他CPU会一直循环重试。这也是实现原子性的条件之一。
成功执行CAS指令的CPU可以确保其他CPU可以看到修改的值(可见性)。并且各个CPU看到的CAS操作的顺序跟代码中的顺序是一致的(有序性)。

总之,CAS能够保证原子操作的原子性、可见性、有序性和互斥性这四个要素。这些特性共同确保了CAS的原子操作正确性,使其可以实现线程同步等功能。所以,CAS之所以可以保证原子性,关键在于它是CPU提供的原子指令,内部可以锁总线并包含连续的三步原子操作,这些特征共同满足原子操作的四个要素,从而实现了原子性。

字符编码

Unicode 和 ANSI 的区别

Unicode 和 ANSI 是两种字符编码标准,主要区别如下:

字符集范围不同:
- Unicode 表示的字符范围更广,包含了绝大多数世界上的文字,可以表示几乎所有的字符。Unicode 的最新版本支持超过 136,000 个字符。
- ANSI 只支持 256 个字符,主要是西欧语言的字符。
编码方式不同:
- Unicode 使用 2 个字节表示一个字符,所以每个字符有 65,536 个值可用。这种编码方式叫做 UTF-16。
- ANSI 使用 1 个字节表示一个字符,每个字符只有 256 个值可用。
兼容性不同:
- Unicode 建立的初衷就是为了解决不同语言字符之间的兼容问题,所以具有很好的兼容性。可以同时支持多种语言。
- ANSI 由于只支持 256 个字符,兼容性较差,不适合 Internationalization(国际化)应用。
Processing 不同:
- Unicode 需要专门的文本处理方式,比如 Unicode 字符串比较、搜索等都需要专门的算法和函数来实现。
- ANSI 可以直接使用字符串的默认处理函数,更简单。

所以总体来说,Unicode 比 ANSI 更加强大和通用。现代应用越来越多采用 Unicode 标准来支持多语言。但 ANSI 由于简单易用,在一些场景下也还是有应用。

字符编码和字符编码方式是什么关系？

字符编码:指为一组字符指定的数字值,它决定了每个字符被存储或传输时对应的二进制代码。常见的字符编码有 ASCII、ISO-8859-1、GBK、Unicode 等。
字符编码方式:是指对字符编码的具体实现方式。一种字符编码可以有多种编码方式。例如:
- Unicode 字符编码可以通过 UTF-8、UTF-16、UTF-32 等编码方式来实现。
- GBK 字符编码就对应一种 GBK 编码方式。

两者的关系可以简单理解为:字符编码 = 字符集 + 编码方式

字符集定义了包含哪些字符,比如 ASCII 的字符集 just 包含英文字符,Unicode 包含全球大多数的字符。
编码方式则定义了如何使用比特位来表示字符集中的每个字符,比如 UTF-8 使用 1-4 个字节,UTF-16 一般使用 2 个字节。

所以,编码方式是实现字符编码的具体方法。一种字符编码可以有多种编码方式,但一种编码方式只对应一种字符编码。编码方式的不同会导致在存储、传输和兼容性上产生影响:

存储:不同编码方式的字符可能对应不同数量的字节,会影响文件大小或数据库存储空间。
传输:字节数量的不同会影响传输的带宽要求。
兼容性:只有使用相同的字符编码和编码方式的系统或软件之间才具有良好的兼容性。所以选择恰当的字符编码方式对实现字符编码非常重要。

虚拟内存(Virt) & 常驻内存(Resident) & 共享内存 (Shared)

虚拟内存(Virt):进程地址空间的大小,包括实际使用的物理内存以及交换空间。虚拟内存的值通常比实际的物理内存和交换空间之和要大。
常驻内存(Resident):进程正在使用的物理内存大小。常驻内存是实际分配给进程的物理内存,用于存储进程当前正在使用的数据和指令。
共享内存(Shared):多个进程共享的内存大小。当几个进程共享同一块物理内存时,这个内存既属于其中一个进程的常驻内存,也属于其他进程的共享内存。

所以,我们可以得出:

虚拟内存(Virt) >= 常驻内存(Resident) + 共享内存(Shared)
常驻内存(Resident) = 非共享的物理内存 + 共享内存(Shared)

简而言之:

虚拟内存是进程地址空间的大小,包含实际使用的内存和交换空间。
常驻内存是进程实际正在使用的物理内存大小,包括共享内存和非共享内存。
共享内存是被多个进程共享使用的内存部分。

所以这三者之间存在包含关系和部分重叠的关系。

Free & Available

“Free"表示当前没有被分配使用的内存空间大小。也就是说，这是操作系统内存管理系统中未被分配给任何进程使用的内存。
“Available"则表示当前可用于分配给进程使用的内存空间大小，其中包括空闲的、未被分配的内存以及被分配但未被进程使用的内存。这意味着，“Available"并不只是指未被使用的内存，而是可以被操作系统分配给进程使用的内存空间。

空闲内存：操作系统中未被分配给任何进程使用的内存空间。
操作系统缓存：操作系统使用的缓存，用于加速系统性能。这些缓存通常包括文件系统缓存、页面缓存等。
被回收内存：已经被进程占用但是已经释放的内存空间，这些内存可以被重新分配给其他进程使用。
虚拟内存：系统中使用的虚拟内存，其中包括已经被分配但当前未被使用的虚拟内存空间。

Buffer & Cached

“Buffer"是指操作系统为了提高文件系统性能而使用的一种缓存机制，用于存储正在进行读写操作的数据。当应用程序读取数据时，数据会被缓存到Buffer中，当应用程序写入数据时，数据也会先被缓存到Buffer中，再由操作系统写入磁盘。这样可以减少磁盘IO操作，提高文件系统性能。
“Cached"是指操作系统为了提高系统性能而使用的一种缓存机制，用于存储经常被访问的数据和程序代码。当应用程序访问数据或执行程序时，操作系统会将这些数据和程序代码缓存到Cached中。如果下次应用程序再次访问这些数据或程序代码，操作系统可以直接从Cached中读取，而不需要再次访问磁盘或执行文件系统操作，从而提高系统性能。

区别在于，Buffer主要用于文件系统的读写操作，而Cached则是为了提高系统性能而缓存常用数据和程序代码。另外，Buffer中的数据可能是尚未被写入磁盘的脏数据，而Cached中的数据则是已经被读取或执行的数据。

Huge Page 的作用和利弊

Huge Page是一种增大操作系统页面大小的技术，它将操作系统页面的大小从默认的4KB增大到2MB或更大。它的作用主要是为了提高系统性能，但也存在一些利弊。

作用：

减少TLB（Translation Lookaside Buffer）misses：TLB是用于存储虚拟地址和物理地址之间映射关系的缓存，如果一个进程的工作集大于TLB大小，则会频繁发生TLB缓存失效。使用Huge Page可以减少页表项数量，从而减少TLB缓存失效，提高系统性能。
减少页表大小：Huge Page可以减少页表项数量，从而减少操作系统内核对页表的访问次数，从而提高系统性能。
减少内存碎片：使用Huge Page可以减少内存碎片，从而减少操作系统的内存管理开销。
省去二级页表。4096个连续的小页可以映射到一个Huge Page,所以不需要二级页表,节省内存。

利弊： 利： 性能提高、内存节省等优点

提高系统性能：通过减少TLB缓存失效和页表访问次数，使用Huge Page可以提高系统性能。
减少内存碎片：使用Huge Page可以减少内存碎片，从而提高系统性能。

弊：

内存使用效率降低：使用Huge Page会使每个页面的大小变大，从而可能导致内存使用效率降低，尤其是在内存较少的系统中。
内存碎片。Huge Page需要连续的大块内存支持,如果内存已经被小页式样使用了,无法分配到足够大的连续内存块,会导致内存浪费(碎片)。
可用内存减少：使用Huge Page会使每个页面的大小变大，从而可能导致可用内存减少，尤其是在内存较少的系统中。
可移植性差：不是所有的操作系统和处理器架构都支持Huge Page，因此使用Huge Page可能导致应用程序在不同的系统上的可移植性降低。
不适合小内存设备。Huge Page适合大内存服务器等设备使用,对于内存受限的小设备,Huge Page可能造成过多内存浪费。

X86的虚拟地址，物理地址，逻辑地址

虚拟地址，物理地址和逻辑地址都是在计算机中用于寻址的概念，它们的区别和联系如下：

虚拟地址（Virtual Address）：虚拟地址也称为虚地址，它是由CPU生成的一个地址，用于表示进程中的内存地址。在使用虚拟内存的系统中，虚拟地址可以被映射到物理地址或者磁盘中的交换空间。应用程序通常只能访问虚拟地址，而不是物理地址或逻辑地址。
物理地址（Physical Address）：物理地址是指内存中实际的地址，也称为实地址。操作系统使用内存管理单元（MMU）将虚拟地址转换为物理地址，以便CPU可以访问内存中的数据。物理地址是在系统启动时由操作系统分配给每个进程的。
逻辑地址（Logical Address）：逻辑地址也称为相对地址，是相对于进程的起始地址的偏移量。逻辑地址不同于虚拟地址，它通常是由程序员定义的，并且只在程序内部使用，不涉及到系统内存管理。

虚拟地址、物理地址和逻辑地址之间的联系是通过内存管理单元（MMU）实现的。MMU是一个硬件组件，用于在CPU和内存之间进行地址转换。当应用程序访问虚拟地址时，MMU会将虚拟地址转换为物理地址，并将物理地址发送给内存控制器，从而让CPU可以访问内存中的数据。

另外，虚拟地址和逻辑地址之间的联系是通过链接器和加载器实现的。链接器用于将不同的模块组合成一个可执行文件，而加载器用于将可执行文件加载到内存中并执行。在链接和加载的过程中，逻辑地址会被转换为虚拟地址，从而使应用程序可以访问内存中的数据。

针对逻辑地址和虚拟地址容易被混淆这一点，注明一下

对于一个单模块的应用而言，逻辑地址和虚拟地址是不需要区分的；
但是对于多模块的应用而言，每个模块可能存在相同的逻辑地址，但是当链接之后，他的虚拟地址就不一样了。

内存回收过程

xxxxx

虚拟地址和物理地址的翻译(MMU & TLB)

MMU 首先将虚拟地址分割成多个部分,通常分为页目录索引、页表索引和页内偏移等部分。
MMU 使用页目录索引查询页目录,获得对应页表的基地址。
使用页表索引查询页表,获得对应物理页的基地址。
将物理页基地址和页内偏移相加,获得最终的物理地址。
使用物理地址访问主存,完成地址翻译过程。

举个32位地址的例子: 虚拟地址:32 bit

页目录索引:10 bit (0-1023)
页表索引:10 bit (0-1023)
页内偏移:12 bit (0-4095)

用虚拟地址的高10位查询页目录,获得页表基地址
用虚拟地址的中间10位索引页表,获得物理页基地址
物理页基地址的低12位就是页内偏移,与虚拟地址的低12位相同
物理页基地址+页内偏移=物理地址

所以,一个32位的虚拟地址会被翻译成一个32位的物理地址。在翻译过程中,MMU根据页目录和页表建立的映射关系,将虚拟地址的高20位映射为物理地址的高20位,低12位不变。

这个过程需要MMU访问2级页表,即页目录和页表,每个页表又需要一个物理内存页来存储,所以会占用一定的物理内存。但通过这种多级页表可以实现虚拟地址到物理地址的映射,使得每个进程有自己独立的虚拟地址空间。

所以,总结来说,虚拟地址到物理地址的翻译是MMU通过多级页表实现的地址映射过程。它将虚拟地址分割成多个部分,依次查询各级页表,获取最终的物理地址,使进程获得连续的虚拟地址空间,这是操作系统提供给进程虚拟化内存访问的基础。

MMU MMU的主要功能包括:

地址映射:将虚拟地址翻译为物理地址,使进程拥有独立的虚拟地址空间。
内存保护:控制进程的内存访问权限,保护进程不被其他进程非法访问。
地址转换支持:支持线性地址到物理地址的转换,也支持线性地址到线性地址的转换。
缓存管理:管理缓存的使用,提高内存访问性能。MMU可以选择将虚拟地址映射到物理内存还是映射到缓存。

具体来说,MMU主要包括以下几个部件:

页表基址寄存器(Page Table Base Register):存放页表的物理地址。
页目录基址寄存器(Page Directory Base Register):页表的物理地址寄存器,用于2级页表。
页表/页目录(Page Table/Directory):保存虚拟页到物理页映射关系的页表,由软件维护。
TLB(Translation Lookaside Buffer):快表,存储部分虚拟地址到物理地址的映射,加速地址转换。
比较器(Comparator):比较地址并控制是否触发缺页中断或异常。
管理器(Control Logic):控制MMU各部件的行为。

当CPU对内存进行访问时,会首先检查TLB是否存在对应的地址映射,如果存在(TLB命中),直接获得物理地址;如果不存在(TLB缺失),会访问页表获得映射关系,并将其加载到TLB,然后获得物理地址。所以,MMU是实现虚拟内存和内存保护的关键所在。它通过快表TLB和多级页表加速虚拟地址到物理地址的转换,使每个进程都拥有独立的虚拟地址空间,保护进程免受非法访问。MMU的工作机制是现代操作系统管理内存的基础。

TLB TLB是 Translation Lookaside Buffer 的缩写,翻译为查找缓冲器。它是MMU中的一个高速缓存,用于存储最近使用的虚拟地址到物理地址的映射关系,加速地址转换。当CPU需要访问内存时,会先检查TLB是否存在对应虚拟地址的映射关系,如果存在,直接使用物理地址访问内存,这个过程称为TLB命中。如果TLB中不存在对应关系,会触发TLB缺失,CPU需要访问页表获取映射关系,然后将其更新到TLB,再访问内存。所以,TLB的主要作用是加速地址转换,避免每次地址转换都需要访问内存中的页表。由于TLB是MMU的一部分,访问TLB的速度很快,这大大提高了地址转换效率。但是,TLB空间有限,只能存放部分映射关系。当访问一个不在TLB中的虚拟地址时,需要通过页表进行地址转换,这个过程效率较低。所以,TLB的效率在很大程度上依赖于TLB命中率。

TLB一般有完全相联和组相联两种结构,主要区别是:

完全相联:任意虚拟地址可以与TLB中任意一个槽相关联。查找过程需要遍历所有的TLB项,但可用性好,冲突概率低。
组相联:将TLB划分成多个组,每个虚拟地址只能映射到其中一个组。查找过程只需要在一个组内遍历,速度更快,但可用性和冲突性能差一些。

TLB的管理包括:

回收策略:当TLB空间不足时,需要将部分条目移除,常用策略为FIFO、LRU、随机替换等。
虚拟地址反向映射:在TLB中同时存放物理地址到虚拟地址的反向映射,用于快速检索虚拟地址。
TLB刷新:当页表内容更改时,需要刷新TLB中对应条目,保证映射关系的同步。

TLB作为MMU的高速缓存,对提高地址转换效率非常关键。不同的TLB结构、管理策略在命中率和成本之间进行权衡,以达到最佳的性能。TLB技术的运用使得虚拟内存得以高效实现。

Drop Cache以后可用内存不增加的主要原因

pending

Buddy 分配器 & Slab 分配器

buddy

![[Pasted image 20230424211438.png]]

slab

内存碎片 & 内存整理

内部碎片 内部碎片是由于系统分配给进程的空间大于其所申请的大小，处于（操作系统分配的用于装载某一进程的内存）区域内部或页面内部的存储块，占有这些区域或页面的进程并不使用这个存储块。而在进程占有这块存储块时，系统无法利用它。直到进程释放它，或进程结束时，系统才有可能利用这个存储块。

原因因为所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址或者因为MMU的分页机制的限制，决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时，因为没有适合大小的内存，所以它可能会获得 44字节、48字节等稍大一点的字节，因此由所需大小四舍五入而产生的多余空间就叫内部碎片。

外部碎片 外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域，即处于任何两个已分配区域或页面之间的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。

原因频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间，就会产生外部碎片。假设有一块一共有100个单位的连续空闲内存空间，范围是0-99。如果你从中申请一块内存，如10个单位，那么申请出来的内存块就为0-9区间。这时候你继续申请一块内存，比如说5个单位大，第二块得到的内存块就应该为10-14区间。如果你把第一块内存块释放，然后再申请一块大于10个单位的内存块，比如说20个单位。因为刚被释放的内存块不能满足新的请求，所以只能从15开始分配出20个单位的内存块。现在整个内存空间的状态是0-9空闲，10-14被占用，15-24被占用，25-99空闲。其中0-9就是一个内存碎片了。如果10-14一直被占用，而以后申请的空间都大于10个单位，那么0-9就永远用不上了，变成外部碎片。

内存整理

**异步模式：**内存碎片整理最常用的模式，在此模式中不会进行阻塞(但是时间片到了可以进行主动调度)，也就是此种模式不会对文件页进行处理，文件页用于映射文件数据使用，这种模式也是对整体系统压力较小的模式。
轻同步模式：**当异步模式整理不了更多内存时，有两种情况下会使用轻同步模式再次整理内存：1.明确表示分配的不是透明大页的情况下；2.当前进程是内核线程的情况下。这个模式中允许大多数操作进行阻塞(比如隔离了太多页，需要阻塞等待一段时间)。这种模式会处理匿名页和文件页，但是不会对脏文件页执行回写操作，而当处理的页正在回写时，也不会等待其回写结束。
**同步模式：**所有操作都可以进行阻塞，并且会等待处理的页回写结束，并会对文件页、匿名页进行回写到磁盘，所以导致最耗费系统资源，对系统造成的压力最大。它会在三种情况下发生：
1. 从cma中分配内存时；
2. 调用alloc_contig_range()尝试分配一段指定了开始页框号和结束页框号的连续页框时；
3. 通过写入1到sysfs中的/vm/compact_memory文件手动实现同步内存碎片整理。