[^0]: Additionally, the name “Utopia” translates to 乌托邦 in Chinese.

简介

TLB的介绍，请看

页表相关

理论基础

大体上是应用访问越随机， 数据量越大，pgw开销越大。

ISCA 2013 shows the pgw overhead in big memory servers.

or ISCA 2020 Guvenilir 和 Patt - 2020 - Tailored Page Sizes.pdf

机器配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# shaojiemike @ snode6 in ~/github/hugoMinos on git:main x [11:17:05]
$ cpuid -1 -l 2
CPU:
      0x63: data TLB: 2M/4M pages, 4-way, 32 entries
            data TLB: 1G pages, 4-way, 4 entries
      0x03: data TLB: 4K pages, 4-way, 64 entries
      0x76: instruction TLB: 2M/4M pages, fully, 8 entries
      0xff: cache data is in CPUID leaf 4
      0xb5: instruction TLB: 4K, 8-way, 64 entries
      0xf0: 64 byte prefetching
      0xc3: L2 TLB: 4K/2M pages, 6-way, 1536 entries
# if above command turns out empty
cpuid -1 |grep TLB -A 10 -B 5
# will show sth like

L1 TLB/cache information: 2M/4M pages & L1 TLB (0x80000005/eax):
    instruction # entries     = 0x40 (64)
    instruction associativity = 0xff (255)
    data # entries            = 0x40 (64)
    data associativity        = 0xff (255)
L1 TLB/cache information: 4K pages & L1 TLB (0x80000005/ebx):
    instruction # entries     = 0x40 (64)
    instruction associativity = 0xff (255)
    data # entries            = 0x40 (64)
    data associativity        = 0xff (255)
L2 TLB/cache information: 2M/4M pages & L2 TLB (0x80000006/eax):
    instruction # entries     = 0x200 (512)
    instruction associativity = 2-way (2)
    data # entries            = 0x800 (2048)
    data associativity        = 4-way (4)
L2 TLB/cache information: 4K pages & L2 TLB (0x80000006/ebx):
    instruction # entries     = 0x200 (512)
    instruction associativity = 4-way (4)
    data # entries            = 0x800 (2048)
    data associativity        = 8-way (6)

OS config

default there is no hugopage(usually 4MB) to use.

1
2
3
4
5
6
7
8
9
10

$ cat /proc/meminfo | grep huge -i
AnonHugePages:      8192 kB
ShmemHugePages:        0 kB
FileHugePages:         0 kB
HugePages_Total:       0
HugePages_Free:        0
HugePages_Rsvd:        0
HugePages_Surp:        0
Hugepagesize:       2048 kB
Hugetlb:               0 kB

explained is here.

设置页表大小

other ways: change source code

1. way1: Linux transparent huge page (THP) support allows the kernel to automatically promote regular memory pages into huge pages, cat /sys/kernel/mm/transparent_hugepage/enabled but achieve this needs some details.
2. way2: Huge pages are allocated from a reserved pool which needs to change sys-config. for example echo 20 > /proc/sys/vm/nr_hugepages. And you need to write speacial C++ code to use the hugo page

1
2
3
4

# using mmap system call to request huge page
mount -t hugetlbfs \
	-o uid=<value>,gid=<value>,mode=<value>,pagesize=<value>,size=<value>,\
	min_size=<value>,nr_inodes=<value> none /mnt/huge

without recompile

But there is a blog using unmaintained tool hugeadm and iodlr library to do this.

1
2
3

sudo apt install libhugetlbfs-bin
sudo hugeadm --create-global-mounts
sudo hugeadm --pool-pages-min 2M:64

So meminfo is changed

1
2
3
4
5
6
7
8
9
10

$ cat /proc/meminfo | grep huge -i
AnonHugePages:      8192 kB
ShmemHugePages:        0 kB
FileHugePages:         0 kB
HugePages_Total:      64
HugePages_Free:       64
HugePages_Rsvd:        0
HugePages_Surp:        0
Hugepagesize:       2048 kB
Hugetlb:          131072 kB

using iodlr library

1

git clone 

应用测量

Measurement tools from code

1
2
3
4
5
6

# shaojiemike @ snode6 in ~/github/PIA_huawei on git:main x [17:40:50]
$ ./investigation/pagewalk/tlbstat -c '/staff/shaojiemike/github/sniper_PIMProf/PIMProf/gapbs/sssp.inj -f /staff/shaojiemike/github/sniper_PIMProf/PIMProf/gapbs/benchmark/kron-20.wsg -n1'
command is /staff/shaojiemike/github/sniper_PIMProf/PIMProf/gapbs/sssp.inj -f /staff/shaojiemike/github/sniper_PIMProf/PIMProf/gapbs/benchmark/kron-20.wsg -n1
K_CYCLES   K_INSTR      IPC DTLB_WALKS ITLB_WALKS K_DTLBCYC  K_ITLBCYC  DTLB% ITLB%
324088     207256      0.64 733758     3276       18284      130         5.64  0.04
21169730   11658340    0.55 11802978   757866     316625     24243       1.50  0.11

平均单次开销(开始到稳定)：
dtlb miss read need 2450 cycle ，itlb miss read need 4027 cycle

案例的时间分布：

• 读数据开销占比不大，2.5%左右
• pagerank等图应用并行计算时，飙升至 22%
  • bfs 最多就是 5%，没有那么随机的访问。
• 但是gemv 在65000 100000超内存前，即使是全部在计算，都是0.24%
  • 原因：访存模式：图应用的访存模式通常是随机的、不规则的。它们不像矩阵向量乘法（gemv）等应用那样具有良好的访存模式，后者通常以连续的方式访问内存。连续的内存访问可以利用空间局部性，通过预取和缓存块的方式减少TLB缺失的次数。
• github - GUOPS can achive 90%
• DAMOV - ligra - pagerank can achive 90% in 20M input case

gemm

• nomal gemm can achive 100% some situation
  • matrix too big can not be filled in cache, matrix2 access jump lines so always cache miss
  • O3 flag seems no time reduce, beacause there is no SIMD assembly in code
  • memory access time = pgw + tlb access time + load data 2 cache time

the gemm‘s core line is

1
2
3
4
5
6
7
8
9
10
11
12

for(int i=0; i<N; i++){
   // ignore the overflow, do not influence the running time.
   for(int j=0; j<N; j++){
      for(int l=0; l<N; l++){
            // gemm
            // ans[i * N + j] += matrix1[i * N + l] * matrix2[l * N + j];

            // for gemm sequantial
            ans[i * N + j] += matrix1[i * N + l] * matrix2[j * N + l];
      }
   }
}

and real time breakdown is as followed. to do

1. first need to perf get the detail time

bigJump

manual code to test if tlb entries is run out

1
2
3
4
5
6
7
8
9
10
11
12
13
14

$ ./tlbstat -c '../../test/manual/bigJump.exe 1 10 100'
command is ../../test/manual/bigJump.exe 1 10 100
K_CYCLES   K_INSTR      IPC DTLB_WALKS ITLB_WALKS K_DTLBCYC  K_ITLBCYC  DTLB% ITLB%
2002404    773981      0.39 104304528  29137      2608079    684        130.25  0.03

$ perf stat -e mem_uops_retired.all_loads -e mem_uops_retired.all_stores -e mem_uops_retired.stlb_miss_loads -e mem_uops_retired.stlb_miss_stores ./bigJump.exe 1 10 500
Number read from command line: 1 10 (N,J should not big, [0,5] is best.)
result 0
 Performance counter stats for './bigJump.exe 1 10 500':

          10736645      mem_uops_retired.all_loads
         532100339      mem_uops_retired.all_stores
             57715      mem_uops_retired.stlb_miss_loads
         471629056      mem_uops_retired.stlb_miss_stores

In this case, tlb miss rate up to 47/53 = 88.6%

Big bucket hash table

using big hash table

other apps

Any algorithm that does random accesses into a large memory region will likely suffer from TLB misses. Examples are plenty: binary search in a big array, large hash tables, histogram-like algorithms, etc.

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

无

Introduction

This set consists of

volume3: Memory management(paging), protection, task management, interrupt and exception handling, multi-processor support, thermal and power management features, debugging, performance monitoring, system management mode, virtual machine extensions (VMX) instructions, Intel® Virtualization Technology (Intel® VT), and Intel® Software Guard Extensions (Intel® SGX).

AMD64 Architecture Programmer’s Manual (3336 pages)

more graph and easier to read.

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html

GLIBC

GLIBC（GNU C Library）是Linux系统中的标准C库，它提供了许多与程序执行和系统交互相关的功能。GLIBC是应用程序与操作系统之间的接口，提供了许多系统调用的包装函数和其他基础功能，使应用程序能够访问操作系统提供的服务和资源。

GLIBC的主要功能包括：

1. 标准C函数：GLIBC实现了C语言的标准库函数，例如字符串处理、内存操作、文件操作、数学函数等。它为应用程序提供了基础的编程功能和操作接口。
2. 系统调用封装：GLIBC封装了许多底层的系统调用，例如文件I/O、进程管理、网络通信等。它提供了更高级别的API函数，使开发者能够更方便地进行系统编程。
3. 内存管理：GLIBC提供了内存分配和管理的函数，例如malloc、free、realloc等。这些函数允许应用程序在运行时动态分配和释放内存，提供了对内存资源的灵活控制。
4. 多线程支持：GLIBC提供了对多线程编程的支持，包括线程创建、同步原语、线程局部存储等功能。它使得开发者能够编写多线程的并发程序。

与上下文切换开销的关系

上下文切换与GLIBC之间没有直接关系。上下文切换是操作系统的概念，是在进程或线程之间切换执行权的过程。GLIBC作为C库，封装了一些系统调用和基础功能，但并不直接参与上下文切换的过程。

然而，GLIBC的性能和效率可以影响上下文切换的开销。GLIBC的实现方式、性能优化以及与操作系统内核的协作方式，可能会对上下文切换的效率产生影响。例如，GLIBC的线程库（如pthread）的设计和性能特性，以及对锁、条件变量等同步原语的实现方式，都可能会影响多线程上下文切换的开销。

因此，尽管GLIBC本身不直接执行上下文切换，但它的设计和实现对于多线程编程和系统性能仍然具有重要的影响。

安装最新版本

ubuntu换源

在PPA。改系统的glibc十分的危险，ssh连接，ls命令等，都需要用到。会导致ssh连接中断等问题。

从源码安装

不推荐，可能会遇到库依赖。比如缺少bison和gawk。详细依赖见

1
2
3
4
5
6
7
8
9

mkdir $HOME/glibc/ && cd $HOME/glibc
wget http://ftp.gnu.org/gnu/libc/glibc-2.32.tar.gz
tar -xvzf glibc-2.32.tar.gz
mkdir build 
mkdir glibc-2.32-install
cd build
~/glibc/glibc-2.32/configure --prefix=$HOME/glibc/glibc-2.32-install
make
make install

寻找动态链接库

您可以使用以下方法来查找libstdc++库的位置：

1. 使用g++或gcc命令查找：如果您的系统上安装了g++或gcc编译器，您可以使用以下命令来查找libstdc++库的位置：

1

g++ -print-file-name=libstdc++.so

或者

1

gcc -print-file-name=libstdc++.so

2. 使用ldconfig命令查找：ldconfig是Linux系统中用于配置动态链接器的命令。您可以运行以下命令来查找libstdc++库的路径：

1

ldconfig -p | grep libstdc++.so

3. 在默认路径下查找：libstdc++通常位于标准的系统库路径中。在大多数Linux发行版中，libstdc++的默认安装路径为/usr/lib或/usr/lib64。您可以在这些目录中查找libstdc++的库文件。

如果您找到了libstdc++库的路径，您可以将其添加到CMakeLists.txt中的CMAKE_CXX_FLAGS变量中，如之前的回答中所示。

请注意，如果您正在使用的是Clang编译器（clang++），则默认情况下它将使用libc++作为C++标准库，而不是libstdc++。如果您确实希望使用libstdc++，需要显式指定使用-stdlib=libstdc++标志。例如：

1

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -stdlib=libstdc++")

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

无

上下文切换

• 根据geekculture的博客的说法
• 上下文主要指的是CPU的寄存器状态，状态越多(上下文越多)，切换时开销就越大。
  • 包括程序计数器(program counters,PC)，栈指针SP，通用寄存器等。还有virtual memory mappings, file descriptor bindings, and credentials.虚拟内存映射、文件描述符绑定和凭据？
• 类型可以分成三类
  • to do

上下文切换的开销

According to 2007 paper

1. direct costs
   1. The processor registers need to be saved and restored,
   2. the OS kernel code (scheduler) must execute,
   3. the TLB entries need to be reloaded,
   4. and processor pipeline must be flushed
2. cache interference cost or indirect cost of context switch.
   1. context switch leads to cache sharing between multiple processes, which may result in performance degradation.

何时上下文切换

进程或线程的上下文切换可以在多种情况下发生，下面列举了一些常见的情况：

1. 抢占调度：当操作系统采用抢占式调度算法时，更高优先级的进程或线程可能会抢占当前运行的进程或线程的CPU时间片，从而导致上下文切换。
2. 时间片耗尽：操作系统通常使用时间片轮转算法来分配CPU时间。当进程或线程的时间片用尽时，操作系统会进行上下文切换，将CPU分配给其他进程或线程。
3. 阻塞和等待：当一个进程或线程发起阻塞的系统调用（如I/O操作）或等待某个事件发生时，操作系统会将其从运行状态切换到阻塞状态，并切换到另一个可运行的进程或线程。
4. 中断处理：当发生硬件中断（如时钟中断、设备中断）或软件中断（如异常、信号），操作系统会中断当前进程或线程的执行，保存其上下文，并转而处理中断服务例程。完成中断处理后，操作系统会恢复中断前的进程或线程的上下文，继续其执行。
5. 多核处理器间的迁移：在多核处理器系统中，进程或线程可能会从一个核心切换到另一个核心，以实现负载均衡或遵循其他调度策略。

需要注意的是，上下文切换是操作系统内核的责任，它根据调度策略和内核的算法来管理进程和线程的切换。上下文切换的具体发生时机和行为取决于操作系统的设计和实现。

进程上下文切换 context switch

保存下来的上下文，会存储在系统内核中，并在任务重新调度执行时再次加载进来。这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

基本原理

• 由于操作系统的抽象: 进程间需要隔离(地址空间，使用的文件描述符，访问权限等) 和执行状态。
• 所以进程间的切换和通讯会触发内核调度器。
• 正如线程Threads将执行单元与进程分离一样，如果将内存隔离、执行状态和特权分离与进程解耦也有好处。

主要的开销

• 进程的状态越多(上下文越多)，切换时开销就越大
  • virtual memory mappings, file descriptor bindings, and credentials.虚拟内存映射、文件描述符绑定和凭据？
  • 线程就是共享了大部分
• 硬件实现的isolation and privilege separation开销是很小的
  • 如果TLB中的页表条目带有地址空间标识符,那么切换上下文只需要一个系统调用和加载一个CPU寄存器就可以完成。
  • 也就是说,硬件实现的内存和特权隔离所需要的实际开销是很小的,主要只是: 1. 一个系统调用,通知OS进行上下文切换 2. 加载一个CPU寄存器,该寄存器包含新的地址空间ID 3. TLB中的对应页表条目标记为无效
  • 随后的指令访问会自动加载新的地址转换信息到TLB。

进程上下文切换的开销

包括以下几个方面：

• 寄存器保存和恢复：在上下文切换过程中，当前进程的寄存器状态需要保存到内存中，包括程序计数器、堆栈指针、通用寄存器等。而切换到新进程时，之前保存的寄存器状态需要重新加载到寄存器中。
• 缓存的数据一致性：需要确保数据的一致性，通常会通过缓冲区刷新、写回操作或者使用写时复制等技术来保证数据的完整性。
• 内存映射切换：每个进程都有自己的内存空间，包括代码、数据和堆栈。在上下文切换时，需要切换内存映射，将当前进程的内存空间从物理内存中解除映射，同时将新进程的内存空间映射到物理内存中。
• 虚拟内存切换：如果系统使用虚拟内存管理，上下文切换还需要涉及虚拟内存的切换，包括页表的更新和TLB（转换后备缓冲器）的刷新。
  • 当虚拟内存更新后，TLB 也需要刷新，内存的访问也会随之变慢。特别是在多处理器系统上，缓存是被多个处理器共享的，刷新缓存不仅会影响当前处理器的进程，还会影响共享缓存的其他处理器的进程。
• I/O状态切换：当前进程可能涉及到正在进行的I/O操作，如读取或写入文件、网络通信等。在上下文切换时，需要保存和恢复与I/O相关的状态，以确保之后能够正确地继续进行这些I/O操作。
• 调度和管理开销：上下文切换过程本身需要一定的调度和管理开销，包括选择下一个要执行的进程、更新进程控制块、维护就绪队列等。

进程切换到不同核时保持数据一致

1. CL-DM：核的私有缓存之间,通过缓存一致性协议 MESI协议
2. REG-DM：寄存器的数据：在进程上下文切换的过程中，系统会保存当前进程的状态，包括进程的程序计数器、寄存器、CPU标志寄存器和堆栈指针等等。

线程切换

线程与进程上下文切换开销的不同

• 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源。这些资源在上下文切换时是不需要修改的。
• 另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

相对于进程上下文切换，线程上下文切换通常更快，这是因为线程共享相同的地址空间和其他资源，因此上下文切换只需要切换线程的执行状态和部分寄存器，省去了一些额外的开销。

以下是线程上下文切换相对于进程上下文切换的一些优势和省去的时间开销：

1. 虚拟内存和页表切换：在进程切换时，由于每个进程都有自己独立的虚拟地址空间和页表，切换进程需要切换虚拟内存映射和页表，这会涉及到TLB的刷新和地址空间切换。而线程切换时，线程共享相同的地址空间和页表，因此无需切换虚拟内存和页表，节省了这部分开销。
2. 上下文切换时间：进程切换通常需要保存和恢复更多的上下文信息，包括寄存器、堆栈指针、文件描述符表等。而线程切换只需要切换线程的执行状态和部分寄存器，上下文切换时间相对较短。
3. 内核数据结构切换：进程切换时，可能涉及到一些内核数据结构的切换和更新，例如进程描述符、文件表等。而线程切换通常只需要更新线程控制块（Thread Control Block，TCB），而无需更新其他内核数据结构，减少了额外的开销。

尽管线程上下文切换相对较快，但仍然需要一些时间和开销，包括以下方面：

1. 寄存器切换：线程上下文切换仍然需要保存和恢复部分寄存器的状态，尤其是通用寄存器和程序计数器。
2. 栈切换：线程切换时，可能需要切换线程的栈空间，包括用户态栈和内核态栈。这涉及到栈指针的调整和栈的切换。
3. 调度开销：线程切换通常是由操作系统的调度器进行调度和管理的，因此线程上下文切换可能涉及到调度算法的执行和调度队列的操作。

需要注意的是，线程上下文切换的快速性是相对于进程上下文切换而言的，具体的开销和时间取决于系统的设计、硬件的性能和操作系统的实现。不同的操作系统和硬件平台可能会有不同的上下文切换开销。

流程与原理

如果要能清晰的回答这一点，需要对OS的页表管理和上下午切换的流程十分了解。

基本概念

Page Table Isolation

Page Table Isolation(页面表隔离)是一种为了解决Meltdown等CPU安全漏洞而提出的硬件优化机制。

其主要思想是将操作系统内核和用户空间的页面表隔离开来,实现内核地址空间与用户地址空间的隔离。

具体来说,Page Table Isolation 主要包括以下措施:

• 为内核空间维护单独的页面表,不与任何用户程序共享。
• 在切换到用户模式时,切换到用户程序自己的页面表。
• 这样内核和用户程序的地址翻译是完全隔离的。
• 当用户程序请求切换到内核模式时,切换回内核专用的页面表。
• 硬件禁止用户模式程序访问内核空间的虚拟地址。

这种机制可以阻止用户程序直接读取内核内存,防止Meltdown类攻击获得内核敏感信息。

当前主流的x86处理器通过在TLB中添加PTI(Page Table Isolation)位实现了此机制,来隔离内核地址空间。这成为了重要的安全优化之一。

页表管理 under PTI

由于PTI的存在，内核维护了两套 页表。

用户态切换的额外开销包括：

1. 改变页面表基地址。改变CR3寄存器需要100cycle
2. TLBmisses 可能增多,因为用户态和内核态不再共享TLB项,可能导致缓存本地化的下降。

PCID

进程上下文标识符（PCID） 是一项 CPU 功能，它允许我们在切换页表时通过在 CR3 中设置一个特殊位来跳过刷新整个 TLB。这使得切换页表（在上下文切换或内核进入/退出时）更便宜。但是，在支持 PCID 的系统上，上下文切换代码必须将用户和内核条目都从 TLB 中清除。用户 PCID TLB 刷新将推迟到退出到用户空间，从而最大限度地降低成本。有关PCID / INVPCID详细信息，请参阅 intel.com/sdm。

在没有 PCID 支持的系统上，每个 CR3 写入都会刷新整个 TLB。这意味着每个系统调用、中断或异常都会刷新 TLB

不同核上同一个进程的不同线程的Intel PCID 是相同的吗

对于同一个进程的不同线程,当它们运行在不同的物理核心上时,其Intel PCID (进程上下文ID)是相同的。

主要原因如下:

PCID是用于区分不同进程地址空间的标识符。同一进程的线程共享相同的地址空间。
所以操作系统会为同一进程的所有线程分配相同的PCID,无论它们运行在哪个物理核心上。
当线程在物理核心之间迁移时,不需要改变PCID,因为地址空间没有改变。
线程迁移后,新的核心会重新使用原有的PCID加载地址翻译表,而不是分配新的PCID。
这确保了同进程不同线程使用统一的地址映射,TLB内容可以直接重用,无需刷新。
相反,不同进程之间必须使用不同的PCID,才能隔离地址映射,避免TLB冲突。
所以操作系统只会在进程切换时改变PCID,而线程切换保持PCID不变。

综上,对于同一进程的不同线程,无论运行在哪个物理核心,其PCID都是相同的。这使线程可以重用TLB项,是多线程架构的重要优化手段。同进程线程使用统一PCID,不同进程必须使用独立PCID。

PCID vs ASID

PCID（Process Context Identifier）和 ASID（Address Space Identifier）都是用于优化页表切换的技术

• PCID使用一个全局的PCID寄存器，用于标识页表项。而ASID则是在每个页表项中直接包含ASID字段。
• 作用范围：PCID主要用于标识整个页表缓存（TLB）中的页表项。ASID则是用于标识每个页表项。

量化

测量的理论基础

Quantifying the cost of context switch

• 设计实验：对照实验，来剔除时间段内 system call 和 cache degradation的影响。
  • sched setaffinity() and sched setscheduler()
  • SCHED FIFO and give them the maximum priority.
• repeat to avg/erase the error

可用代码

1
2
3
4
5
6
7
8
9

# shaojiemike @ hades0 in ~/github/contextSwitch2007 on git:master x [15:59:39] C:10
$ sudo ./measureSwitch
time2 with context swith:       1.523668        1.509177        1.507308
measureSwitch: array_size = 0, stride = 0, min time2 = 1.507308008149266

# shaojiemike @ hades0 in ~/github/contextSwitch2007 on git:master x [16:04:15]
$ sudo ./measureSingle
time1 without context switch:   0.727125        0.655041        0.689502
measureSingle: array_size = 0, stride = 0, min time1 = 0.655041355639696

• 阅读代码后时间单位是us microseconds, 论文里是3.8 us,我们的机器是0.85 us。
• 小问题：这个跨核了吗？

实践测试

Tsuna的2010年的博客
code in https://github.com/tsuna/contextswitch 机器配置在实验结果后。

• syscalls 使用 gettid()
• 进程上下文切换使用futex来切换。包含futex system calls.开销
  • sched_yield让出CPU使用权,强制发生进程切换.
• 线程切换还是使用的futex.只不过线程通过 pthread_create创建来执行函数, 而不是fork
• 线程切换只使用shed_yield().并且设置SCHED_FIFO 和 sched_priority
  • sched_yield()函数的作用是使当前进程放弃CPU使用权,将其重新排入就绪队列尾部。但是如果就绪队列中只有这一个进程,那么该进程会立即再次获得CPU时间片而继续执行。必须有其他等待进程且满足调度条件才会真正发生切换。
  • 如果使用了taskset绑定1个核组，应该就能测量上下文切换。

1
2
3
4
5
6
7
8
9
10

# snode6
$ sudo taskset 0x3 ./timetctxsw2
2000000  thread context switches in 486078214ns (243.0ns/ctxsw)
$ sudo taskset 0x1 ./timetctxsw2
2000000  thread context switches in 1071542621ns (535.8ns/ctxsw)
# hades0
$ sudo taskset 0x3 ./timetctxsw2
2000000  thread context switches in 89479052ns (44.7ns/ctxsw)
$ sudo taskset 0x1 ./timetctxsw2
2000000  thread context switches in 566817108ns (283.4ns/ctxsw)

如上，snode6应该是550ns

说明:

1. 同名机器从上到下为：No CPU affinity 和 With CPU affinity 和 With CPU affinity to CPU 0
2. ()内为。额外添加设置SCHED_FIFO 和 sched_priority的结果。
3. * 意味着没有sudo权限。报错sched_setscheduler(): Operation not permitted
4. x 报错taskset: 设置 pid 30727 的亲和力失败: 无效的参数
5. system calls 理解成 用户态和内核态转换的开销
6. 根据博客的数据，虚拟化会使得开销增大2～3倍。

问题：

1. 两个thread context的区别是什么？
   只使用shed_yield().并且设置SCHED_FIFO 和 sched_priority
2. taskset 限制了能运行的核。
3. 这个实验测量了 在两个核间的线程切换吗？没绑定应该是多核
   1. 为什么taskset绑定在同一个核反而变慢了呢。snode6
      1. timetctxsw2 340 -> 550
      2. timetctxsw 括号内数据 1712 -> 2225
   2. 同一个核有资源竞争吗？

运行strace -ff -tt -v taskset -a 1 ./timetctxsw2. 应该是不需要strace的，为什么需要记录syscall的信息呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# snode6 
2000000  thread context switches in 22987942914ns (11494.0ns/ctxsw)

# snode6 without strace
$ sudo taskset -c 1 ./timetctxsw2
2000000  thread context switches in 1073826309ns (536.9ns/ctxsw)
$ sudo taskset -a 1 ./timetctxsw2
2000000  thread context switches in 1093753292ns (546.9ns/ctxsw)
$ sudo taskset 1 ./timetctxsw2
2000000  thread context switches in 1073456816ns (536.7ns/ctxsw)

# hades
2000000  thread context switches in 20945815905ns (10472.9ns/ctxsw)
# icarus
2000000  thread context switches in 19053536242ns (9526.8ns/ctxsw)
2000000  thread context switches in 17573109017ns (8786.6ns/ctxsw)
2000000  thread context switches in 18538271021ns (9269.1ns/ctxsw)

尝试解释不同机器的差异

猜想：

1. Intel新产品的硬件确实有特殊设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

 shaojiemike @ snode6 in ~/github/contextswitch on git:master o [19:46:27]
$ sudo ./cpubench.sh
model name : Intel(R) Xeon(R) CPU E5-2695 v4 @ 2.10GHz
2 physical CPUs, 18 cores/CPU, 2 hardware threads/core = 72 hw threads total

hades1# ./cpubench.sh
model name : AMD EPYC 7543 32-Core Processor 1.5 ~ 3.7GHz
2 physical CPUs, 32 cores/CPU, 2 hardware threads/core = 128 hw threads total

# shaojiemike @ icarus0 in ~/github/contextswitch on git:master o [20:41:39] C:1
$ ./cpubench.sh
model name : Intel(R) Xeon(R) Platinum 8358 CPU @ 2.60GHz
2 physical CPUs, 32 cores/CPU, 1 hardware threads/core = 64 hw threads total

ubuntu@VM7096-huawei:~/github/contextswitch$ sudo ./cpubench.sh 
model name : Intel(R) Xeon(R) Silver 4110 CPU @ 2.10GHz
2 physical CPUs, 8 cores/CPU, 2 hardware threads/core = 32 hw threads total

2. 软件的不同

glic 版本使用ldd --version获得。OS影响调度算法，内核影响切换机制，编译器影响代码优化，GLIBC影响系统调用开销。

代码分析

1. sched_setscheduler() 是一个用于设置进程调度策略的函数。它允许您更改进程的调度策略以及与之相关的参数。具体来说，sched_setscheduler() 函数用于将当前进程（通过 getpid() 获取进程ID）的调度策略设置为实时调度策略（SCHED_FIFO）。实时调度策略是一种优先级调度策略，它将进程分配给一个固定的时间片，并且仅当进程主动释放 CPU 或者其他高优先级的实时进程出现时，才会进行上下文切换。
2. /sys/bus/node/devices/node0/cpumap 存储了与特定 NUMA 节点（NUMA node）关联的 CPU 核心映射信息。cpumap 文件中的内容表示与 node0 相关的 CPU 核心的映射。每个位置上的值表示相应 CPU 核心的状态，常见的取值有：
   • 0：表示该 CPU 核心不属于 node0。
   • 1：表示该 CPU 核心属于 node0。
     这种映射信息可以帮助系统管理员和开发人员了解系统的 NUMA 结构，以及每个 NUMA 节点上的 CPU 核心分布情况。通过查看这些信息，可以更好地优化任务和进程的分配，以提高系统的性能和效率。

1
2
3
4
5
6
7
8
9

# shaojiemike @ snode6 in ~/github/contextswitch on git:master x [22:37:41] C:1
$ cat /sys/bus/node/devices/node0/cpumap
00,003ffff0,0003ffff
# shaojiemike @ snode6 in ~/github/contextswitch on git:master x [23:13:41]
$ cat /sys/bus/node/devices/node1/cpumap
ff,ffc0000f,fffc0000
# 与taskset结合 设置 亲和性
taskset `sed 's/,//g;s/^/0x/' /sys/bus/node/devices/node0/cpumap` exe
taskset 0x00003ffff00003ffff exe

基于lmbench

根据1996的论文，需要考虑几个方面的内容：

1. 传统的测量取最小值当作是两进程只进行上下文切换的开销。作者认为真实应用有更大的working set (cache footprint)影响。
2. 在调用context switches时，传统的会包含syscall。比如 write read。这部分pipe overhead varies between 30%
   and 300% of the context switch time
3. to do

http://lmbench.sourceforge.net/cgi-bin/man?keyword=lmbench&section=8

实践代码

别人实验结果

知乎实验 5 微秒左右

• 进程切换实验设计：基于#include <unistd.h> /pipe()的父子进程的write和read system calls
  • 被1996年文章批判了，syscall开销过大。
• 线程切换实验设计：使用pthread代替fork 其余一样。

论文数据

实验环境：

• 处理器：Intel Xeon X5650 2.66 GHz 6 core CPUs
• 操作系统：FreeBSD 11.0 (amd64)
• 基于信号量semaphore实现会比基于互斥锁mutex快

根据Light-weight Contexts的数据：

• 进程切换：4.25 微秒 (0.86)，4250*2.66=11305 cycles
• kernel线程切换：4.12 (0.98)
• user线程切换 - 基于系统调用：1.71 (0.06) ～ 4548 cycles
  • 内核态用户态切换开销： ～ 1.5 微秒 ～ 4000 cycles
• user线程切换 - 基于glibc的用户汇编：0.2472 ~ 657 cycles

注意，括号内为十次执行的标准差

解释与组成

• 0.25 微秒 寄存器信息传递
• 2 微秒 虚拟地址映射（TLB flush all？）
• 2 微秒 同步与调度（进程切换）
  • 原因是同一进程或不同进程中的两个内核线程之间切换时执行的内核代码基本上是相同的。

需要进一步的研究学习

1. 在测量上下文开销的时候，进程和线程的上下午切换开销往往差不多，这是为什么，是因为TLBflush的占比小没有拉开差距吗

在测量上下文切换开销时，进程和线程的切换开销可能会相对接近，这可能是由于以下几个原因：

1. TLB（Translation Lookaside Buffer）的刷新：TLB是用于高速缓存虚拟地址到物理地址映射的硬件结构。当发生进程或线程切换时，TLB中的缓存项可能需要刷新，以确保新的地址映射有效。虽然线程切换只涉及部分的TLB刷新，但刷新的开销相对较小，因此在总的上下文切换开销中可能没有明显拉开差距。

2. 寄存器和上下文切换：无论是进程切换还是线程切换，都需要保存和恢复一部分寄存器的状态和执行上下文。这部分的开销在进程和线程切换中是相似的。

3. 内核操作和调度开销：无论是进程还是线程切换，都需要涉及内核的操作和调度。这包括切换内核栈、更新调度信息、切换上下文等操作，这些开销在进程和线程切换中也是相似的。

需要注意的是，实际上下文切换的开销是受到多个因素的影响，如处理器架构、操作系统的实现、硬件性能等。具体的开销和差距会因系统的不同而有所差异。在某些情况下，线程切换的开销可能会稍微小一些，但在其他情况下，可能会存在较大的差距。因此，一般情况下，不能简单地将进程和线程的上下文切换开销归为相同或明显不同，具体的测量和评估需要结合实际系统和应用场景进行。

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

PIM 最优调度遇到的问题

1. 理解上下文切换的具体过程，linux内核的角度
   1. 理解相关概念的使用 ASID PCID
   2. 用户态，内核态的概念，切换的细节以及开销
      1. 内核态的代码是共享的吗？内核态的操作有什么？
2. 各部分的时间占比
3. 学会测量时间

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

Quantifying The Cost of Context Switch 2007，ExpCS

lmbench: Portable tools for performance analysis，1996 USENIX ATC

Light-weight Contexts: An OS Abstraction for Safety and Performance

参考 kernel 文档

基础知识

切换开销

线程在核间切换的开销是极小的(Java uses lots of threads but threads have become significantly faster and cheaper with the NPTL in Linux 2.6.)，与其考虑切换开销，不如注意不同优先级线程同一个核竞争的问题。

静态/动态优先级 与 调度域

• 基本概念：
• 静态/动态优先级：见 深入理解Linux内核 - 第七章 进程调度 - 调度算法。
• 调度域：见 深入理解Linux内核 - 第七章 进程调度 - 多处理器系统中任务队列的平衡 - 调度域^1

创建

在C++中，有几种方式可以实现线程的创建。下面是一些常见的方法：

1. 使用 C++11 标准库的 std::thread 类

这是C++11标准引入的线程库，使用起来非常方便。你可以直接创建一个 std::thread 对象并传递一个函数或可调用对象（如lambda表达式）。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12

#include <iostream>
#include <thread>

void threadFunction() {
    std::cout << "Hello from thread!" << std::endl;
}

int main() {
    std::thread t(threadFunction);  // 创建线程，立刻执行 threadFunction
    t.join();  // 等待线程执行完毕
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12

#include <iostream>
#include <thread>

void threadFunction() {
    std::cout << "Hello from thread!" << std::endl;
}

int main() {
    std::thread t(threadFunction);  // 创建线程，子线程立刻开始执行
    t.join();  // 等待子线程执行完毕
    return 0;
}

2. 使用 std::async 和 std::future

std::async 可以用于异步执行任务，返回一个 std::future 对象，你可以通过这个对象获取任务的执行结果。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12

#include <iostream>
#include <future>

int asyncFunction() {
    return 42;
}

int main() {
    std::future<int> result = std::async(asyncFunction);  // 异步执行函数
    std::cout << "Result: " << result.get() << std::endl;  // 获取结果
    return 0;
}

3. 使用 POSIX 线程（Pthreads）

在使用较早的C++版本或在一些特定的操作系统（如Linux）下，pthread 是创建和管理线程的常用方式。需要包含 <pthread.h> 头文件。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>
#include <pthread.h>

void* threadFunction(void*) {
    std::cout << "Hello from POSIX thread!" << std::endl;
    return nullptr;
}

int main() {
    pthread_t thread;
    pthread_create(&thread, nullptr, threadFunction, nullptr);  // 创建POSIX线程
    pthread_join(thread, nullptr);  // 等待线程结束
    return 0;
}

4. 使用Boost库

Boost库提供了丰富的线程管理功能，使用起来与标准库类似，但需要安装Boost库。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12

#include <boost/thread.hpp>
#include <iostream>

void threadFunction() {
    std::cout << "Hello from Boost thread!" << std::endl;
}

int main() {
    boost::thread t(threadFunction);  // 创建Boost线程
    t.join();  // 等待线程执行完毕
    return 0;
}

5. 使用原生操作系统API

可以直接调用操作系统提供的API来创建线程，例如在Windows上使用 CreateThread，在Unix/Linux上使用 pthread_create。

Windows上的示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <windows.h>
#include <iostream>

DWORD WINAPI threadFunction(LPVOID lpParam) {
    std::cout << "Hello from Windows thread!" << std::endl;
    return 0;
}

int main() {
    HANDLE thread = CreateThread(
        nullptr,         // 默认安全属性
        0,               // 默认堆栈大小
        threadFunction,  // 线程函数
        nullptr,         // 线程函数参数
        0,               // 默认创建标志
        nullptr);        // 返回线程ID

    WaitForSingleObject(thread, INFINITE);  // 等待线程结束
    CloseHandle(thread);  // 关闭线程句柄
    return 0;
}

总结

• C++11 std::thread 是最常用和推荐的方式，简单易用且跨平台。
• std::async 更适合用于需要返回值的异步操作。
• POSIX pthread 适合在类Unix系统上使用，适应性强但需要更多的低层管理。
• Boost线程库 提供了丰富的功能，适合需要额外功能的场合。
• 操作系统API 更适合需要与操作系统深度集成的场景。

修改

线程独占的信息很少，一般就是线程名的获取和设置。

线程名

1
2
3
4
5
6
7
8
9
10
11
12

#include <sys/prctl.h>

if (prctl(PR_SET_NAME, ("ACL_thread")) != 0) {
    ASCEND_LOGE("set thread name failed!");
}

char thread_name[16];  // 线程名称最大为16字节，包括终止符
if (prctl(PR_GET_NAME, thread_name, 0, 0, 0) == 0) {
    std::cout << "Thread name: " << thread_name << std::endl;
} else {
    std::cerr << "Error getting thread name" << std::endl;
}

处理器亲和性

• 简单测试: 使用taskset -c 0-4 {command},可以实现命令绑定在编号0-3核上。
• 代码内实现: c++内通过pthread_setaffinity_np函数实现。
  • 绑定到NUMA node后，利用OS的自动CPU负载均衡即可。

* `htop -p pid` 里 `a` 选项可以显示已有的亲和性设置
* `ps -p pid` 可以看见CMD相同。

数据竞争

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>
#include <thread>
#include <vector>
#include <mutex>

int globalVariable = 0;
std::mutex globalMutex; // 互斥锁

void incrementGlobal() {
    std::lock_guard<std::mutex> lock(globalMutex); // 锁定互斥锁
    globalVariable++;
}

int main() {
    std::vector<std::thread> threads;
    for (int i = 0; i < 10; ++i) {
        threads.push_back(std::thread(incrementGlobal));
    }

    for (auto& thread : threads) {
        thread.join();
    }

    std::cout << "Final value of globalVariable: " << globalVariable << std::endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <iostream>
#include <map>
#include <thread>
#include <mutex>
#include <sys/syscall.h>
#include <unistd.h>

class ThreadManager {
public:
    // 获取ThreadManager实例
    static ThreadManager& getInstance() {
        static ThreadManager instance;
        return instance;
    }

    // 注册线程并分配核心
    void registerThread() {
        std::lock_guard<std::mutex> lock(mutex_);
        pid_t tid = syscall(SYS_gettid);  // 获取当前线程的TID
        if (threadMap_.find(tid) == threadMap_.end()) {
            int core = getNextCore();
            threadMap_[tid] = core;
            std::cout << "Thread " << tid << " assigned to core " << core << std::endl;
        }
    }

    // 获取分配给特定TID的核心
    int getCore(pid_t tid) {
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = threadMap_.find(tid);
        if (it != threadMap_.end()) {
            return it->second;
        }
        return -1; // 如果未找到TID，则返回-1
    }

private:
    std::map<pid_t, int> threadMap_;  // 线程ID和核心的映射表
    std::mutex mutex_;                // 保护threadMap_的互斥锁
    int nextCore_;                    // 下一个分配的核心号

    ThreadManager() : nextCore_(0) {}  // 构造函数初始化nextCore_

    // 获取下一个核心号（简单轮询策略）
    int getNextCore() {
        int core = nextCore_;
        nextCore_ = (nextCore_ + 1) % std::thread::hardware_concurrency();  // 轮询分配核心
        return core;
    }

    // 禁止复制构造和赋值操作符
    ThreadManager(const ThreadManager&) = delete;
    ThreadManager& operator=(const ThreadManager&) = delete;
};

// 测试线程函数
void threadFunction() {
    ThreadManager::getInstance().registerThread();  // 注册线程
    // 线程的其他操作
}

int main() {
    std::thread t1(threadFunction);
    std::thread t2(threadFunction);

    t1.join();
    t2.join();

    return 0;
}

待研究

1. pthread to learn
2. 父子线程进程的退出影响

参考文献

文件系统简介

计算机文件系统是操作系统的一个重要组成部分,它管理计算机存储设备上的文件,负责文件存储、读取和组织等功能。文件系统的主要作用包括:

• 文件存储与寻址:文件系统负责在存储设备上对文件进行存取,需要找到文件在存储设备上的位置。常见的寻址机制有:
  • FAT表:使用文件分配表记录每个文件所占用簇的位置。
  • inode:为每个文件分配一个inode,记录文件存储位置、大小、访问时间等元信息。
• 文件组织与优化:文件系统负责组织硬盘空间,常见的组织结构包括:
  • 目录结构:将文件组织成目录/子目录的树形层次结构。
  • 碎片整理:通过碎片整理优化空间利用率。
  • 块大小:通过调整块大小来改善IO性能。
• 访问控制:管理文件访问权限、用户组等信息,确保访问安全。
  • 高级功能:一些文件系统实现了高级功能,如快照、数据压缩、加密等。
  • 系统完整性:提供一致性检验、崩溃恢复机制来保证文件系统完整可靠。

常见的文件系统包括Windows上的FAT、NTFS,Unix/Linux上的ext、XFS、Btrfs等。

文件系统的设计对操作系统的性能、安全性有很大影响。一个优秀的文件系统应提供高效的IO访问、良好的安全控制和数据完整性保障。选择正确的文件系统对不同场景也很重要。

评估文件系统

• 性能:读写速度、响应时间、并发支持如何,可以测试IO性能。
• 可靠性:数据完整性保证、Crash可恢复性如何,测试崩溃恢复。
• 安全性:访问控制、防篡改机制如何,测重写、破坏后的数据恢复。
• 容量:最大文件大小、卷大小、目录容量如何,测试边界极限。
• 扩展性:可线性扩展还是需要重构,测试大容量情况下的性能。
• 元数据:元信息组织结构,是否支持快速查找、高级索引。
• 分配机制:如何分配和回收空间,是否会产生碎片。
• 一致性:是否保证读写顺序一致性,如何支持缓存与本地IO。
• 插件机制:是否可以通过插件扩展功能,如压缩、加密等。
• 兼容性:是否兼容主流平台和老系统,测试迁移和交互兼容性。

基本概念：数据分块存储

文件储存在硬盘上，硬盘的最小存储单位叫做”扇区”（Sector）。每个扇区储存512字节（相当于0.5KB）。

但是就像内存读取也不会只读一个字节， 硬盘的存储和读取都是按照Block进行的(比如,4KB即连续八个 sector组成一个 block。)

早期：FAT文件系统

早期文件分配表（File Allocate Table，FAT）

链表结构解决了文件和物理块映射的问题。

小结

• 常见的FAT12、FAT16、FAT32格式,用于早期Windows系统。
• 优点：简单易用,支持跨平台
• 缺点：非常占用内存, 效率和安全性不高。
  • 比如 1T 的硬盘，如果块的大小是 1K，那么就需要 1G 个 FAT 条目。
  • 通常每个 FAT 条目还会存一些其他信息，需要 2~3 个字节， FAT条目总共占用 2-3G 的内存空间，才能用来管理 1T 的硬盘空间。

常见：基于inode的文件系统

基于 inode(index node的数据结构) 的传统文件系统。文件数据被存储不同块里面，文件的元数据信息就会被存储在inode里面。

特点

• 在Unix/Linux中广泛使用的文件系统,如Ext、XFS等。
• 每个文件都有一个对应的inode,记录文件元信息和数据块位置。
• 操作系统通过inode找到文件内容,支持权限控制等高级功能。
• 效率高,安全可靠,但inode会占用一定存储空间。

文件操作流程

由于inode号码与文件名分离

• 删除流程
  • 删除一个文件名，就会使得inode节点中的”链接数”减1。当这个值减到0，表明没有文件名指向这个inode，系统就会回收这个inode号码，以及其所对应block区域。
  • 直接删除inode，能够起到删除(包含特殊字符)文件的作用find ./* -inum 节点号 -delete
• 移动文件或重命名文件
  • 只是改变文件名，不影响inode号码；

inode存储Block信息

为了解决数据变化问题，它引入了3个存储指针设计。

• 直接指针可以直接指向数据块本身，数据块就是保存数据的块
• 间接指针是在前面的指针指针不够的时候才会启用，间接指针可以看成链表那样，间接指针会指向一个个索引块，这块本身又是一个数据块的指针也是只是指向存储数据块。
• 第3类指针，指向一个二级索引块，二级索引块的指针还可以指向新的索引块

大小占用

• 每个inode节点的大小固定，一般是128字节或256字节。
• inode节点的总数，在格式化时就给定，一般是每1KB或每2KB就设置一个inode。
• 每个文件都必须有一个inode，因此有可能发生inode已经用光，但是硬盘还未存满的情况。这时，就无法在硬盘上创建新文件。
• 每个inode都有一个号码，操作系统用inode号码来识别不同的文件。

1
2
3
4
5
6
7
8
9
10

$ df -hi .
Filesystem     Inodes IUsed IFree IUse% Mounted on
/dev/sda2         56M  5.1M   51M   10% /
或者
/dev/sda2      58605568 5321132 53284436   10% /

# 每个inode节点的大小，一般是128字节或256字节。
$ sudo dumpe2fs -h /dev/sda2 | grep "Inode size"
dumpe2fs 1.45.5 (07-Jan-2020)
Inode size:               256

58605568/256 = 222928 个 inode节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

$ fdisk -l
Disk /dev/sda: 894.26 GiB, 960197124096 bytes, 1875385008 sectors
Disk model: INTEL SSDSC2KB96
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
Disklabel type: gpt
Disk identifier: 86F8050E-C9E7-4BDB-8B0C-89E20B013FF6

Device     Start        End    Sectors   Size Type
/dev/sda1   2048       4095       2048     1M BIOS boot
/dev/sda2   4096 1875382271 1875378176 894.3G Linux filesystem

$ sudo fdisk -l /dev/sda2
Disk /dev/sda2: 894.26 GiB, 960193626112 bytes, 1875378176 sectors (512 bytes per sector)
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes

1875378176/228928 = 8192(8K) 个 sector 对应一个inode节点

一个inode节点对应 4MB的空间？

目录、软链接、硬链接

• 目录：目录是一种特殊的文件，它的inode节点中存储的是文件名和inode号码的对应关系。
• 软链接：软链接拥有自己的inode，但是文件内容就是一个快捷方式。
  • 命令 ln -s /etc/nginx/config link_config
  • 文件A和文件B的inode号码虽然不一样，但是文件A的内容是文件B的路径。读取文件A时，系统会自动将访问者导向文件B。因此，无论打开哪一个文件，最终读取的都是文件B。这时，文件A就称为文件B的”软链接”（soft link）或者”符号链接（symbolic link）。
  • 文件A指向文件B的文件名，而不是文件B的inode号码，文件B的inode”链接数”不会因此发生变化。
• 硬链接：多个文件名指向同一个inode号码。
  • 命令 ln main.c link_main.c

软链接、硬链接区别与使用场景

在大部分常见场景下,硬链接是更优的选择：

1. 硬链接是一个真实文件,不会无效,更可靠。软链接指向的文件移动或删除后会失效。
2. 硬链接与原文件性能一致,软链接需要在查询时重新解析路径。

硬链接也有一些限制：

1. 不能跨文件系统,软链接可以实现跨文件系统的链接。
2. 目录无法创建硬链接,只能软链接。

日志文件系统

• NTFS 和 Ext3 是日志文件系统，它们和 FAT 最大的区别在于写入到磁盘中的是日志，而不是数据。
• 日志文件系统会先把日志写入到内存中一个高速缓冲区，定期写入到磁盘。
• 日志写入是追加式的，不用考虑数据的覆盖。
• 一段时间内的日志内容，会形成还原点。这种设计大大提高了性能，当然也会有一定的数据冗余。

日志文件系统 与 inode 文件系统的关系

1. 日志文件系统是一种技术,可以建立在多种文件系统之上,包括inode文件系统。
2. inode文件系统是一种文件系统架构,每个文件都有一个inode保存元信息。ext、xfs等都是这种架构。
3. 但两者不是必然关联的,日志文件系统技术也可以用在非inode型文件系统上。

常见名词及文件系统：MBR、GPT和FAT、EXT2

前两者是磁盘分区格式，后两者是文件系统格式。

MBR、GPT是两种比较常见的磁盘分区格式，而且对于磁盘分区而言，目前也主要是这两种格式。一个分区是一个存储设备上的一块独立区域，用户可以针对这块区域进行单独管理。

• NFS:网络文件系统,允许通过网络访问文件,可应用在分布式系统。
• ZFS:引入了pooled storage和checksum等特性的128位文件系统。
• HFS:Mac OS使用的层次化文件系统,使用B*树对元数据进行组织。

实践：fdisk的结果

• “Disk label type”表示当前磁盘的分区形式，
• dos表示磁盘分区形式为MBR，
• gpt表示磁盘分区形式为GPT

Windows NTFS文件系统

New Technology File System (NTFS):Windows NT引入的文件系统,使用主文件表(MFT)来管理文件,支持高级功能如权限控制等。

• NTFS卷上的任何事物都是文件(为了与平时使用的文件相区别，以下用FILE特指)，
• FILE通过主文件表(master file table, MFT)来确定其在卷上的位置，
• 每个FILE有固定大小，一般为1KB。
• FILE记录了文件的所有数据，每个数据以一个属性来表示，如文件名、文件长度、文件的时间等都是属性，文件的内容也是一个属性，每个属性有一个特征码。
• 属性数据较小时能够存放在FILE记录中，称为驻留的属性，反之为非驻留的属性，通过Data Runs来保存其存储索引表。
  • 这一点与FAT文件系统不同，FAT文件系统只在目录区保存了文件的首簇号，还要通过FAT表链接关系才能确定文件的全部存放位置。
  • Data Runs在一个FILE记录存放不下时还可以用扩展属性，增加FILE记录来保存，即一个文件可以有多个FILE记录。

NTFS的同层目录采用B+树结构，按文件(夹)名保持有序，通过文件号指向文件夹内的文件。文件夹的目录项较少时可以直接存储在文件夹的FILE记录中，目录项较多时占用数据簇，建立INDX记录，存放各目录项的属性。

NTFS文件系统一共由16个“元文件”构成

Linux常见 EXT文件系统的发展简介

ext1

• 优点：1992 年的 ext 使用在 Linux 内核中的新虚拟文件系统（VFS）抽象层。
  • 与之前的 MINIX 文件系统不同的是，ext 可以处理高达 2 GB 存储空间并处理 255 个字符的文件名。
• 缺点：原始的时间戳（每个文件仅有一个时间戳，而不是今天我们所熟悉的有 inode、最近文件访问时间和最新文件修改时间的时间戳。）

ext2

• 优点：提供了 GB 级别的最大文件大小和 TB 级别的文件系统大小。
• 缺点：
  • 将数据写入到磁盘的时候，系统发生崩溃或断电，则容易发生灾难性的数据损坏。
  • 随着时间的推移，由于碎片（单个文件存储在多个位置，物理上其分散在旋转的磁盘上），它们也遭受了严重的性能损失。

ext3

• 2001 年 11 月在 2.4.15 内核版本中被采用到 Linux 内核主线中。
• 优点：使用日志来解决断电数据不一致问题，和 20 世纪 90 年代后期的其它文件系统一样，如微软的 NTFS。

ext4

• 2008年在 2.6.28 内核版本中被加入到了 Linux 主线。
• 优点：
  • 支持大文件系统，
    • ext3 文件系统使用 32 位寻址，这限制它仅支持 2 TiB 文件大小和 16 TiB 文件系统系统大小
    • ext4 使用 48 位的内部寻址，理论上可以在文件系统上分配高达 16 TiB 大小的文件，其中文件系统大小最高可达 1000000 TiB（1 EiB）
  • 分配方式改进，显著提高读写性能
    • 区段(extent)
      • 是一系列连续的物理块 (最多达 128 MiB，假设块大小为 4 KiB），可以一次性保留和寻址。使用区段而不是 block可以减少给定文件所需的 inode 数量，并显著减少碎片并提高写入大文件时的性能。
    • 多块分配(multiple block allocation)
      • ext3 为每一个新分配的块调用一次块分配器。当多个写入同时打开分配器时，很容易导致严重的碎片。
      • 多块分配(multiple block allocation)允许一次性分配大量的连续文件块，以降低碎片并且有利于 RAID 设备的并行写入
    • 延迟分配（delayed block allocation）
      • ext4 使用延迟分配（delayed block allocation），这允许它合并写入并更好地决定如何为尚未提交的写入分配块。
      • 延迟分配允许 ext4 等待分配将写入数据的实际块，直到它准备好将数据提交到磁盘。（相比之下，即使数据仍然在往写入缓存中写入，ext3 也会立即分配块。）
      • 当缓存中的数据累积时，延迟分配块允许文件系统对如何分配块做出更好的选择，降低碎片（写入，以及稍后的读）并显著提升性能。
    • 持久的预分配( allocation without initialization)
      • 在为文件预分配磁盘空间时，大部分文件系统必须在创建时将零写入该文件的块中。
      • ext4 允许替代使用 fallocate()，它保证了空间的可用性（并试图为它找到连续的空间），而不需要先写入它。这显著提高了写入和将来读取流和数据库应用程序的写入数据的性能。
  • 提高了对碎片的抵抗力
    • ext2 和 ext3 都不直接支持在线碎片整理 —— 即在挂载时会对文件系统进行碎片整理。
    • ext4 通过 e4defrag 解决了这个问题，且是一个在线、内核模式、文件系统感知、块和区段级别的碎片整理实用程序。

Nas 防止碎片，开启预分配

实践问题： Nas 的 ext4 挂载被识别成NTFS

估计是有一层转换，类似的软件有 UFS Explorer

磁盘读写原理

读写操作分层

对于磁盘的一次读请求，

• 首先经过虚拟文件系统层（VFS Layer），
• 其次是具体的文件系统层（例如Ext2），
• 接下来是Cache层（Page Cache Layer）、
• 通用块层（Generic Block Layer）、
• I/O调度层（I/O Scheduler Layer）、
• 块设备驱动层（Block Device Driver Layer），
• 最后是物理块设备层（Block Device Layer）。

Page Cache层

• 为了提高Linux操作系统对磁盘访问的性能。Cache层在内存中缓存了磁盘上的部分数据。当数据的请求到达时，如果在Cache中存在该数据且是最新的，则直接将数据传递给用户程序，免除了对底层磁盘的操作，提高了性能。
• 文件Cache分为两个层面，
  • 一是Page Cache，另一个Buffer Cache，每一个Page Cache包含若干Buffer Cache。
  • Page Cache主要用来作为文件系统上的文件数据的缓存来用，尤其是针对当进程对文件有read/write操作的时候。
  • Buffer Cache则主要是设计用来在系统对块设备进行读写的时候，对块进行数据缓存的系统来使用。
• 磁盘Cache有两大功能：预读和回写。
  • 预读其实就是利用了局部性原理，具体过程是：
    • 对于每个文件的第一个读请求，系统读入所请求的页面并读入紧随其后的少数几个页面（通常是三个页面），这时的预读称为同步预读。
    • 对于第二次读请求，
      • 如果所读页面不在Cache中，即不在前次预读的页中，则表明文件访问不是顺序访问，系统继续采用同步预读；
      • 如果所读页面在Cache中，则表明前次预读命中，操作系统把预读页的大小扩大一倍，此时预读过程是异步的，应用程序可以不等预读完成即可返回，只要后台慢慢读页面即可，这时的预读称为异步预读。
    • 任何接下来的读请求都会处于两种情况之一：第一种情况是所请求的页面处于预读的页面中，这时继续进行异步预读；第二种情况是所请求的页面处于预读页面之外，这时系统就要进行同步预读。
  • 回写是通过暂时将数据存在Cache里，然后统一异步写到磁盘中。
    • 通过这种异步的数据I/O模式解决了程序中的计算速度和数据存储速度不匹配的鸿沟，减少了访问底层存储介质的次数，使存储系统的性能大大提高。Linux
    • 2.6.32内核之前，采用pdflush机制来将脏页真正写到磁盘中，什么时候开始回写呢？下面两种情况下，脏页会被写回到磁盘：
      • 在空闲内存低于一个特定的阈值时，内核必须将脏页写回磁盘，以便释放内存。
      • 当脏页在内存中驻留超过一定的阈值时，内核必须将超时的脏页写会磁盘，以确保脏页不会无限期地驻留在内存中。

I/O调度层

• I/O调度层的功能是管理块设备的请求队列。
  • 即接收通用块层发出的I/O请求，缓存请求并试图合并相邻的请求。
  • 并根据设置好的调度算法，回调驱动层提供的请求处理函数，以处理具体的I/O请求。
• 如果简单地以内核产生请求的次序直接将请求发给块设备的话，那么块设备性能肯定让人难以接受，因为磁盘寻址是整个计算机中最慢的操作之一。
• 为了优化寻址操作，内核不会一旦接收到I/O请求后，就按照请求的次序发起块I/O请求。
• 为此Linux实现了几种I/O调度算法，算法基本思想就是通过合并和排序I/O请求队列中的请求，以此大大降低所需的磁盘寻道时间，从而提高整体I/O性能。

常见的I/O调度算法包括

1. Noop调度算法（No Operation）、
2. CFQ（完全公正排队I/O调度算法）、
3. DeadLine（截止时间调度算法）、
4. AS预测调度算法等。

磁盘快速I/O常见机制

Linux系统中请求到达磁盘的一次完整过程，期间Linux一般会通过Cache以及排序合并I/O请求来提高系统的性能。

其本质就是由于磁盘随机读写慢、顺序读写快的磁盘I/O特性。

采用追加写

在进行系统设计时，良好的读性能和写性能往往不可兼得。在许多常见的开源系统中都是优先在保证写性能的前提下来优化读性能。那么如何设计能让一个系统拥有良好的写性能呢？

• 一个好的办法就是采用追加写，每次将数据添加到文件。
• 由于完全是顺序的，所以可以具有非常好的写操作性能。
• 但是这种方式也存在一些缺点：从文件中读一些数据时将会需要更多的时间：
  • 需要倒序扫描，直到找到所需要的内容。
  • 当然在一些简单的场景下也能够保证读操作的性能：
    • 数据是被整体访问，比如HDFS
    • 知道文件明确的偏移量，比如Kafka
  • 在面对更复杂的读场景（比如按key）时，如何来保证读操作的性能呢？
    • 简单的方式是像Kafka那样，将文件数据有序保存，使用二分查找来优化效率；
    • 或者通过建索引的方式来进行优化；
    • 也可以采用hash的方式将数据分割为不同的桶。
  • 以上的方法都能增加读操作的性能，但是由于在数据上强加了数据结构，又会降低写操作的性能。
    • 比如如果采用索引的方式来优化读操作，那么在更新索引时就需要更新B-tree中的特定部分，这时候的写操作就是随机写。
  • 那么有没有一种办法在保证写性能不损失的同时也提供较好的读性能呢？
  • 一个好的选择就是使用LSM-tree。
    • LSM-tree与B-tree相比，LSM-tree牺牲了部分读操作，以此大幅提高写性能。

文件合并和元数据优化

目前的大多数文件系统，如XFS/Ext4、GFS、HDFS，在元数据管理、缓存管理等实现策略上都侧重大文件。

磁盘碎片

不同文件系统的比较

像 FAT 和 FAT32 这类文件系统中，文件紧挨着写入到磁盘中。文件之间没有空间来用于增长或者更新：

NTFS 中在文件之间保留了一些空间，因此有空间进行增长。但因块之间的空间是有限的，碎片也会随着时间出现。

Linux 的日志型文件系统采用了一个不同的方案。与文件相互挨着不同，每个文件分布在磁盘的各处，每个文件之间留下了大量的剩余空间。这就给文件更新和增长留下了很大的空间，碎片很少会发生。

此外，碎片一旦出现了，大多数 Linux 文件系统会尝试将文件和块重新连续起来。

检测命令

在已经挂载的分区中运行 fsck 将会严重危害到你的数据和磁盘。

1
2

umount /path
fsck -fn /path

大于20%需要整理。批评fsck不准的文章：大文件碎片少才是最重要的

NEC 的 Akira Fujita 和 Takashi Sato 在十年前就为 ext4 写了在线整理碎片的工具，因此我们直接拿来用就好了。

1

e4defrag -v /path

碎片整理

方法一：整个磁盘文件备份，格式化，重新搬运。(Liunx 会自动将文件进行连续分布排列。)

方法二：

1
2

# 不要中断，很危险
sudo e4defrag /

常见实践问题

为什么出现坏道之后，硬盘会飞速损耗

坏道分为逻辑坏道，和物理坏道。如果是物理坏道，由于异物或者碰撞导致磁头，盘面受损，会导致物理损坏扩散，应该今早备份数据。

并行下载多个两个文件，存储是交叉的吗？读数据会变慢吗？

场景问题：

1.同时向机械硬盘拷贝多个文件夹，每个文件夹里都有多个小文件。
2.同时解压多个压缩包，每个压缩包有大量的小文件。
3.同时安装多个游戏安装包。
会不会导致交叉存储？会不会导致碎片增加？会不会导致游玩游戏时读取速度变慢？

一般不用担心，有些文件系统会做碎片整理。然后操作系统的缓存写和预读策略也会优化。

硬盘的寿命

对于机械硬盘来讲，反复读写、多线程读写等情况对磁盘使用寿命的影响很低，
但“高温”、“低温”、“尘土”、“外力冲击（跌落）”等情况，会对磁盘的寿命造成较大的影响。

需要进一步的研究学习

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://learn.lianglianglee.com/%E4%B8%93%E6%A0%8F/%E9%87%8D%E5%AD%A6%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F-%E5%AE%8C/30%20%20%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F%E7%9A%84%E5%BA%95%E5%B1%82%E5%AE%9E%E7%8E%B0%EF%BC%9AFAT%E3%80%81NTFS%20%E5%92%8C%20Ext3%20%E6%9C%89%E4%BB%80%E4%B9%88%E5%8C%BA%E5%88%AB%EF%BC%9F.md

https://www.ruanyifeng.com/blog/2011/12/inode.html

https://tech.meituan.com/2017/05/19/about-desk-io.html

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

https://developer.aliyun.com/article/197465

互斥与同步

在进程/线程并发执行的过程中，进程/线程之间存在协作的关系，例如有互斥、同步的关系。

为了实现进程/线程间正确的协作，操作系统必须提供实现进程协作的措施和方法，主要的方法：

• 基于原子操作指令(汇编) —— 测试和置位（Test-and-Set）指令, 或者（如Compare-And-Swap，CAS）
• 锁：加锁、解锁操作；
  • 自旋锁(spin lock， 忙等待锁)，
  • 无等待锁：思想，把当前线程放入到锁的等待队列，然后执行调度程序
• 信号量：P、V 操作；

这两个都可以方便地实现进程/线程互斥，而信号量比锁的功能更强一些，它还可以方便地实现进程/线程同步。

常见问题

悲观锁

1. 读写操作时，需要预先加锁，防止其他进程对资源的访问。
2. 通过互斥锁（Mutex）和信号量（Semaphore）来实现。

乐观锁

1. 在读取或修改共享资源时，并不先进行加锁操作，而是先读取资源，然后在对资源进行写操作时再进行一次比较，看看在这个时间间隔内是否发生了竞争。如果没有发生竞争，就可以将更新后的值写入共享资源，并结束操作；如果发生了竞争，则需要放弃本次更新，并进行重试
2. 通过版本号的方式来实现。在共享资源中记录该资源的版本号，当一个进程想要修改共享资源时，需要先获取当前资源的版本号。如果当前版本号与自己保存的版本号相符，说明没有其他进程在这段时间内修改该资源，则可以进行写操作；如果版本号已经发生变化，则说明有其他进程对该资源进行了修改，当前进程需要放弃本次写操作，更新版本号，重新获取新的资源，并重新执行操作。

原子操作

Test-and-Set 和 Compare-and-Swap (CAS) 都是并发编程中的重要原子操作指令，通常用于同步和处理多线程或多进程环境中的竞争条件。它们的作用是确保某些操作在执行时不会被中断，以保持数据一致性和避免并发冲突。我们来详细了解这两个命令。

1. Test-and-Set (TAS) 指令

• 通常用于控制锁定状态，通过设置标志位来获取锁，它返回原始值（通常是锁状态），用于判断锁是否已经被占用。
• 它通常用于实现自旋锁、互斥锁（mutex）或锁标志位。

它的操作过程如下：

• Test: 检查指定位置（通常是一个布尔标志位或整数）当前的值。
• Set: 将这个位置的值设置为 1 或 “true”。

操作是原子的，即不会被中断或干扰，保证在并发环境下，多个线程或进程不能同时修改同一位置。

用途：

• 实现自旋锁（Spinlock）：线程反复检查一个共享变量，如果该变量表示未被锁定，线程会尝试获得锁。
• 防止竞争条件：确保在并发操作时，只有一个线程能够设置锁标志，其他线程需要等待。

1
2
3
4
5
6

lock = false;

while (Test_and_Set(lock)) {
    // 如果 lock 已经被设置为 true，则继续自旋等待
}
// lock 成功设置为 true，获取锁

2. Compare-and-Swap (CAS) 指令

• 通常用于无锁编程，它通过比较期望值与当前值来决定是否进行更新（检查指定的内存位置的值是否等于一个预期的值，如果相等，则将该位置的值替换为新的值），适用于复杂的数据结构操作。
• 常用于无锁数据结构和其他更高效的并发操作。

它的操作步骤如下：

• Compare: 比较目标内存位置的当前值是否与预期值相等。
• Swap: 如果当前值等于预期值，就将目标位置的值替换为新的值。如果不相等，则什么也不做。

CAS 也具有原子性，这意味着它在操作期间不会被中断。CAS 是实现无锁编程和避免线程同步问题的常用工具，尤其在需要高性能的并发程序中。

用途：

• 实现无锁数据结构（如无锁队列、栈、哈希表等）。
• 实现线程安全的计数器或标志位操作。
• 用于一些算法（如版本控制或并发计数器）中，确保多个线程不冲突地更新共享数据。

1
2
3
4
5
6
7
8

int expected = 10;
int new_value = 20;

if (Compare_and_Swap(&x, expected, new_value)) {
    // 如果 x 的值为 expected (10)，就将 x 更新为 new_value (20)
} else {
    // 如果 x 的值不为 expected，CAS 操作失败
}

3. TAS的汇编实现

• Test-and-Set (TAS) 操作通常可以通过 XCHG 指令（交换）在 x86 汇编中实现。虽然 x86 没有直接的 Test-and-Set 指令，XCHG 被用作实现类似功能的原子操作。

1
2
3
4
5
6

; x86 示例，使用 XCHG 实现 Test-and-Set
; 假设锁变量位于 memory_location
; eax 是存储旧值的寄存器
mov eax, 0          ; eax 设为 0，表示“未锁定”
xchg eax, [lock]    ; 将 eax 与锁变量交换，如果锁变量是 0，就设置为 1
                    ; 如果返回的 eax 仍为 0，说明锁成功设置

4. CAS的汇编实现

• Compare-and-Swap (CAS) 指令在 x86 中有专门的 CMPXCHG 指令，ARM 等其他架构也有类似的原子操作指令（如 LDREX 和 STREX）。

1

CMPXCHG destination, source

1
2
3
4
5
6
7

; x86 示例，使用 CMPXCHG 实现 Compare-and-Swap
; 假设目标内存位置是 lock，期望值是 eax，新的值是 ebx

mov eax, expected_value    ; 将期望的值加载到 eax
mov ebx, new_value        ; 将新的值加载到 ebx
cmpxchg [lock], ebx        ; 比较 [lock] 的值与 eax（期望值），如果相等则将 [lock] 更新为 ebx（新值）
                        ; 如果不相等，eax 会保存 [lock] 的原值

1
2
3
4
5

; ARM 示例，使用 LDREX 和 STREX 实现 CAS
LDREX R0, [lock]    ; 加载锁的当前值到 R0
CMP R0, R1           ; 比较 R0（当前锁的值）与 R1（期望值）
BNE CAS_FAIL         ; 如果不相等，跳转到失败处理
STREX R2, R3, [lock] ; 如果相等，将 R3（新值）写入 [lock]，并将成功标志存储在 R2

atomic 封装

std::atomic 是对 Test-and-Set 和 Compare-and-Swap 等底层原子操作的高级封装，使得 C++ 开发者可以在多线程环境中更方便、更安全地使用这些原子操作。

原子操作（std::atomic）有如下特点：

• 线程安全：原子操作保证了即使在多线程环境下也能正确地修改和读取共享变量。
• 高效：没有加锁开销，适用于需要频繁检查和修改标志的场景。
• 原子操作的限制：std::atomic 只能用于一些简单的类型（如整数、指针和布尔类型），对于复杂的数据结构，仍然需要其他同步机制（如锁）。

1
2
3
4
5
6
7
8
9
10
11

#include <atomic>

std::atomic<bool> isInited(false);

void initFunction() {
    // 原子操作，检查并更新 isInited
    if (!isInited.exchange(true)) { // mutex  std::call_once 和std::once_flag 也可以实现类似功能。
        // 执行初始化逻辑
        // ...
    }
}

1
2
3

std::atomic<int> counter(0);
counter = 5;  // 这种赋值操作不是原子操作，可能导致线程不安全。
int value = counter;  // 直接读取可能没有同步, 导致缓存不一致问题，多个线程读取的值不一定是最新的。

内存顺序：std::memory_order

对于一个线程里的同一个代码块内的无依赖关系的指令，处理器在运行时会重排序乱序执行。这对原子指令也是一样的。但实际生产中，多个原子操作之间，可能会有依赖关系，比如一个线程读取另一个线程写入的数据。为了确保这些依赖关系的正确性，需要使用内存顺序来控制处理器对指令的重排序。

std::atomic 的操作支持指定内存顺序，这控制了编译器和硬件对操作的优化和重排序。常见的内存顺序选项有：

• std::memory_order_relaxed：没有限制，运行时会乱序。
• std::memory_order_acquire 和 std::memory_order_release：分别用于“获取”和“释放”同步，确保操作顺序。
  • std::memory_order_acquire：保证在此操作之前的所有操作不会被重排序到它之后。
  • std::memory_order_release：保证在此操作之后的所有操作不会被重排序到它之前。
• std::memory_order_seq_cst：默认的内存顺序，保证在多线程程序中，所有原子操作按顺序执行，不允许重排序。但性能可能会略受影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <atomic>
#include <iostream>
#include <thread>

std::atomic<int> counter(0);
std::atomic<bool> ready(false);

void producer() {
    counter.store(42, std::memory_order_release);  // 确保 counter 写入在 ready 之前
    ready.store(true, std::memory_order_release);  // 标记准备好
}

void consumer() {
    while (!ready.load(std::memory_order_acquire)) {}  // 等待 ready 为 true
    std::cout << "Counter: " << counter.load(std::memory_order_acquire) << std::endl;
}

int main() {
    std::thread t1(producer);
    std::thread t2(consumer);

    t1.join();
    t2.join();

    return 0;
}

1. 直接赋值：store

在原子操作中，store 用来将一个值存储到原子变量中。与普通赋值不同，store 会确保在多线程环境下，赋值操作是原子性的（即不会被打断）。

1
2

std::atomic<int> counter(0);
counter.store(5, std::memory_order_relaxed);  // 存储 5

• store 会保证在指定的内存顺序下将值存储到原子变量中，因此它是线程安全的。

2. 加载：load

load 用于从原子变量中读取值。它会确保在多线程环境中，读取操作是线程安全的，并且可以指定内存顺序。

1

int value = counter.load(std::memory_order_acquire);  // 从原子变量读取

• load 会确保读取的是正确同步后的值，避免在多线程场景下出现读取错误。

3. 比较并交换：compare_exchange_strong

• compare_exchange_strong（以及 compare_exchange_weak）广泛应用于实现锁和无锁算法。它会尝试将原子变量的值与一个预期值进行比较，如果相同，则将其更新为新值。如果比较失败，原子变量的值不会更改，并且返回 false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

std::atomic<int> value(0);
int expected = 0;
int desired = 42;

if (value.compare_exchange_strong(expected, desired)) {
    std::cout << "CAS succeeded! Value updated to " << value.load() << "\n";
} else {
    std::cout << "CAS failed! Expected: " << expected << ", Actual: " << value.load() << "\n";
}

// 尝试比较并交换
while (!value.compare_exchange_weak(expected, desired)) {
    std::cout << "CAS failed, retrying...\n";
    // 可以执行一些其他的操作或稍微延迟再重试
}
std::cout << "CAS succeeded! Value updated to " << value.load() << "\n";

4. exchange

exchange 是一种常见的原子操作，类似于 store，但它会返回原子变量的先前值。

1

int oldValue = counter.exchange(5);  // 返回更新前的值，并将 counter 设置为 5

• exchange 在多线程环境下是安全的，并且可以返回修改前的值，适用于某些需要获取旧值的场景。

常见锁的优缺点和实现

自旋锁(spinlock)

多线程同步的一种忙等待锁，线程反复检查锁变量是否可用。

• 优点：避免了操作系统进程调度和线程切换，所以自旋锁通常适用在时间比较短的情况下。由于这个原因，操作系统的内核经常使用自旋锁。
• 缺点：如果长时间上锁的话，自旋锁会非常耗费性能，它阻止了其他线程的运行和调度
  • 线程持有锁的时间越长，则持有该锁的线程将被 OS(Operating System) 调度程序中断的风险越大。
• 解决办法：
  • TicketLock 是采用排队叫号的机制。
  • CLHLock和MCSLock通过链表的方式避免了减少了处理器缓存同步，极大的提高了性能，区别在于CLHLock是通过轮询其前驱节点的状态，而MCS则是查看当前节点的锁状态。

1
2
3
4
5
6
7
8
9

std::atomic_flag lock = ATOMIC_FLAG_INIT;

void spinlock() {
    while (lock.test_and_set(std::memory_order_acquire)) {
        // 自旋等待，直到锁被释放
    }
    // 临界区代码
    lock.clear(std::memory_order_release);  // 解锁
}

互斥锁(mutex)

把自己阻塞起来（内核态和用户态之间的切换进入阻塞状态，可能上下文切换），等待重新调度请求。

• 互斥锁的实现
  1. 软件实现：软件互斥锁需要借助操作系统提供的原子操作（如Compare-And-Swap，CAS）来实现 优点是灵活性高 缺点是性能较低，
  2. CAS操作需要三个参数，内存地址A，期望值V，新值N。执行过程如下：
     • 读取内存地址A的原始值，保存在临时变量Value中
     • 比较Value和期待值V是否相等，如果相等则将内存地址A的值更新为新值N
     • 如果内存地址A的值已经被其他线程改变，则不进行更新操作
• TAS（test and set）
  • 一个TAS指令包括两个子步骤，把给定的内存地址设置为1，然后返回之前的旧值。
  1. 硬件实现：硬件互斥锁使用计算机硬件提供的特殊指令（如锁总线指令）来实现。当线程要获取锁时，它会发出一个锁总线指令，这个指令会占用系统总线，使得其他CPU无法读写内存。
     1. 当lock前缀指令执行时，它将锁定处理器总线，确保其他处理器无法同时访问同一内存区域，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>
#include <mutex>
#include <thread>

std::mutex init_mutex_;  // 互斥量，防止多个线程同时初始化

void some_function() {
    // 创建一个 lock_guard 对象，自动锁住 init_mutex_
    std::lock_guard<std::mutex> lock(init_mutex_);

    // 在此作用域内，init_mutex_ 被锁定
    std::cout << "Doing some work inside the critical section...\n";

    // lock_guard 在作用域结束时会自动解锁 mutex
}

int main() {
    std::thread t1(some_function);
    std::thread t2(some_function);

    t1.join();
    t2.join();

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <atomic>

std::mutex mtx;
std::condition_variable cv;
std::atomic<bool> thread_done{false};

void worker_thread() {
    std::this_thread::sleep_for(std::chrono::seconds(2)); // 模拟工作
    std::cout << "Worker thread finished." << std::endl;
    thread_done = true;  // 设置线程完成标志
    cv.notify_one();     // 通知主线程
}

void Final() {
    std::cout << "Final: Waiting for worker thread to finish..." << std::endl;

    // 等待子线程完成
    std::unique_lock<std::mutex> lock(mtx);
    cv.wait(lock, [] { return thread_done.load(); });
    // cv.wait(lock, [this] { return thread_done.load(); }); // in class

    std::cout << "Final: Worker thread finished. Proceeding with cleanup." << std::endl;
}

int main() {
    // 启动子线程
    std::thread t(worker_thread);

    // 在主线程中调用 Final
    Final();

    t.join();  // 等待子线程结束

    return 0;
}

读写锁（ReadWrite Lock）

• 在读操作和写操作之间提供了更细粒度的同步控制。
• 多个线程可以同时获取读锁，但只有一个线程能够获取写锁。
  • 读写锁有三种状态：读加锁状态、写加锁状态和不加锁状态
  • 规则
  • 当读写锁在写加锁模式下，任何试图对这个锁进行加锁的线程都会被阻塞，直到写进程对其解锁。
  • 当读写锁在读加锁模式先，任何线程都可以对其进行读加锁操作，但是所有试图进行写加锁操作的线程都会被阻塞，直到所有的读线程都解锁。
• 缺点：当读者源源不断到来的时候，写者总是得不到读写锁，就会造成不公平的状态。
  • 避免方法： 当处于读模式的读写锁接收到一个试图对其进行写模式加锁操作时，便会阻塞后面对其进行读模式加锁操作的线程。这样等到已经加读模式的锁解锁后，写进程能够访问此锁保护的资源。
• 优点：
  • 读写锁可以提高并发性，允许多个线程同时读取数据，而只有在需要修改数据时才会互斥。
  • 适合对数据结构读的次数远远大于写的情况。

RCU（Read-Copy-Update）

• 对读写锁的一种改进。适用于读多写少场景的数据同步机制。
• 具体内容
  • 并发读取数据不再需要加锁
  • 写数据时，RCU机制通过创建一个副本来实现读写分离，确保在更新过程中没有线程正在读取旧的数据。
    • 写者修改数据前首先拷贝一个被修改元素的副本，然后在副本上进行修改，修改完毕后它向垃圾回收器注册一个回调函数以便在适当的时机执行真正的修改操作。
    • 读者必须提供一个信号给写者以便写者能够确定数据可以被安全地释放或修改的时机。
    • 有一个专门的垃圾收集器来探测读者的信号，一旦所有的读者都已经发送信号告知它们都不在使用被RCU保护的数据结构，垃圾收集器就调用回调函数完成最后的数据释放或修改操作。

通知与同步

适用于大段的修改和同步。

eventfd 事件通知

eventfd 是 Linux 提供的一种用于线程安全的事件通知机制，类似于文件描述符，可以通过读写操作来实现跨线程或跨进程的同步。通过 eventfd，线程或进程可以通过某些事件（例如计数器增减、通知等）来触发其他线程或进程的动作。

eventfd 可以通过两种方式工作：

• 计数器模式：通过 eventfd_write 增加计数器，其他线程或进程可以通过 eventfd_read 来读取这些计数器的值。
• 通知模式：使用 eventfd 进行事件通知，线程或进程通过 eventfd_read 来等待并响应这些事件。

eventfd_read 的功能 : eventfd_read 是一个用于从 eventfd 文件描述符读取事件的系统调用。它会从 eventfd 中读取一个 64 位无符号整数，并返回这个值。这个值通常表示某个事件的状态或计数器的值。

1
2
3
4

#include <sys/eventfd.h>

ssize_t eventfd_read(int efd, uint64_t *value);
ssize_t eventfd_write(int efd, uint64_t value);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <sys/eventfd.h>
#include <unistd.h>
#include <iostream>
#include <cstring>

int main() {
    // 创建 eventfd 文件描述符
    int efd = eventfd(0, EFD_NONBLOCK);
    if (efd == -1) {
        std::cerr << "Failed to create eventfd: " << strerror(errno) << std::endl;
        return -1;
    }

    // 写入事件
    uint64_t u = 1; // 写入一个事件值
    ssize_t s = write(efd, &u, sizeof(u));
    if (s == -1) {
        std::cerr << "Failed to write to eventfd: " << strerror(errno) << std::endl;
        close(efd);
        return -1;
    }

    // 读取事件
    uint64_t read_value;
    s = eventfd_read(efd, &read_value);
    if (s == -1) {
        std::cerr << "Failed to read from eventfd: " << strerror(errno) << std::endl;
    } else {
        std::cout << "Read value: " << read_value << std::endl;
    }

    close(efd);
    return 0;
}

概念题

1
2
3
4

P(S):
  while S <= 0:
    // 等待，直到S大于0
  S = S - 1

1
2

V(S):
  S = S + 1

参考文献

https://www.cswiki.top/pages/f398f1/#blocking-i-o

原文链接：https://blog.csdn.net/qq_15437629/article/details/79116590

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