Posted Updated Architecture10 minutes read (About 1511 words)

Disassembly file: objdump

objdump file

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Disassembly of section .plt:

0000000000402020 <.plt>:
  402020: ff 35 e2 bf 02 00     pushq  0x2bfe2(%rip)        # 42e008 <_GLOBAL_OFFSET_TABLE_+0x8>
  402026: ff 25 e4 bf 02 00     jmpq   *0x2bfe4(%rip)        # 42e010 <_GLOBAL_OFFSET_TABLE_+0x10>
  40202c: 0f 1f 40 00           nopl   0x0(%rax)

0000000000402030 <_Znam@plt>:
  402030: ff 25 e2 bf 02 00     jmpq   *0x2bfe2(%rip)        # 42e018 <_Znam@GLIBCXX_3.4>
  402036: 68 00 00 00 00        pushq  $0x0
  40203b: e9 e0 ff ff ff        jmpq   402020 <.plt>

0000000000402040 <_ZNSo3putEc@plt>:
  402040: ff 25 da bf 02 00     jmpq   *0x2bfda(%rip)        # 42e020 <_ZNSo3putEc@GLIBCXX_3.4>
  402046: 68 01 00 00 00        pushq  $0x1
  40204b: e9 d0 ff ff ff        jmpq   402020 <.plt>

.plt节主要实现了使用过程链接表(Procedure Linkage Table)实现延迟绑定的功能。

openmp相关的执行

omp_outlined函数

问题：objdump 程序 有许多 类似 <.omp_outlined..16>: 的函数，但是main函数里并没有调用。实际openmp是怎么执行这些代码的呢？

在使用了OpenMP指令的C/C++程序编译后,编译器会自动生成一些名为.omp_outlined.的函数。这些函数是OpenMP所需要的运行时支持函数,不是直接在main函数中调用的,其执行方式主要有以下几种:

  1. 一些关键的运行时函数,如线程创建、同步等,是在程序启动时由OpenMP运行时库初始化和直接调用的。
  2. 对于并行region,编译器会在主线程发起并行时调用对应的.omp_outlined.函数创建线程并发布工作。
  3. 一些工作分配,同步等调用也是隐式通过运行时库的支持函数实现的。
  4. 对于并行循环,编译器会将循环体移动到.omp_outlined.函数,在循环分配工作时调用。
  5. 减少指令,作用域变化等也会引发这些函数的调用。

所以.omp_outlined.函数的执行是隐式通过运行时库触发和调度的,不需要用户代码直接调用。它们是OpenMP实现所必须的,由编译器和运行时库协调完成。用户只需要编写OpenMP指令,不必关心具体的调用细节。

总体来说,这是一种让并行执行透明化的实现机制,减少了用户的工作量。

OpenMP的汇编代码

不同平台不同，有GOMP_parallel_start开头的。也有如下x86平台的

1
2
3
4
5
6
7
8
9
10
11
405854:	48 c7 84 24 a0 00 00 	movq   $0x4293b9,0xa0(%rsp)
40585b:	00 b9 93 42 00 
405860:	48 8d bc 24 90 00 00 	lea    0x90(%rsp),%rdi
405867:	00 
405868:	ba 10 5f 40 00       	mov    $0x405f10,%edx
40586d:	be 02 00 00 00       	mov    $0x2,%esi
405872:	4c 89 f9             	mov    %r15,%rcx
405875:	4c 8b 44 24 20       	mov    0x20(%rsp),%r8
40587a:	31 c0                	xor    %eax,%eax
40587c:	e8 ff cb ff ff       	callq  402480 <__kmpc_fork_call@plt>
405881:	48 8b 7c 24 60       	mov    0x60(%rsp),%rdi

这段汇编代码实现了OpenMP中的并行构造,主要执行了以下几个步骤:

  1. 在栈上写入一个常量0x4293b9,可能是team的参数 (48 c7 84 24)
  2. 准备参数,获取rsp+0x90地址到rdi作为第1参数 (%rdi)
  3. 设置edx为0x405f10,可能是kmp_routine函数地址
  4. esi设置为2,可能表示有2个参数
  5. r15设置到rcx,传入线程号参数
  6. r8传入栈上第0x20个参数,可能是void* shareds参数
  7. 清空eax,一些调用约定使用
  8. 调用 __kmpc_fork_call函数,这是OpenMP的runtime库函数,用来并行执行一个函数
    1. kmpc fork multiple parallel call？
  9. 最后将返回值保存在rdi指定的栈空间上

所以这段代码实现了调用OpenMP runtime并行执行一个函数的操作,准备参数,调用runtime API,获取返回值的一个流程。

利用runtime库的支持函数可以实现汇编级别的OpenMP并行性。

readelf

各section位置以及含义，参考文档

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
$ readelf -S bfs.inj
There are 37 section headers, starting at offset 0xbe8e8: 
在文件内 0xbe8e8字节开始

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  序号 节名称               节类型          节的虚拟地址偏移量      节在文件中的偏移量
节大小         每个条目的大小（如果大小固定）  节的标志  节的链接信息    节的额外信息    节的信息对齐方式
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .interp           PROGBITS         00000000004002a8  000002a8
       000000000000001c  0000000000000000   A       0     0     1
  [ 2] .note.gnu.build-i NOTE             00000000004002c4  000002c4
       0000000000000024  0000000000000000   A       0     0     4
  [ 3] .note.ABI-tag     NOTE             00000000004002e8  000002e8
       0000000000000020  0000000000000000   A       0     0     4
  [ 4] .gnu.hash         GNU_HASH         0000000000400308  00000308
       000000000000005c  0000000000000000   A       5     0     8
  [ 5] .dynsym           DYNSYM           0000000000400368  00000368
       00000000000007e0  0000000000000018   A       6     1     8
  [ 6] .dynstr           STRTAB           0000000000400b48  00000b48
       0000000000000b1d  0000000000000000   A       0     0     1
  [ 7] .gnu.version      VERSYM           0000000000401666  00001666
       00000000000000a8  0000000000000002   A       5     0     2
  [ 8] .gnu.version_r    VERNEED          0000000000401710  00001710
       0000000000000110  0000000000000000   A       6     5     8
  [ 9] .rela.dyn         RELA             0000000000401820  00001820
       00000000000000f0  0000000000000018   A       5     0     8
  [10] .rela.plt         RELA             0000000000401910  00001910
       00000000000006c0  0000000000000018  AI       5    24     8
  [11] .init             PROGBITS         0000000000402000  00002000
       000000000000001b  0000000000000000  AX       0     0     4
  [12] .plt              PROGBITS         0000000000402020  00002020
       0000000000000490  0000000000000010  AX       0     0     16
  [13] .text             PROGBITS         00000000004024b0  000024b0
       0000000000026475  0000000000000000  AX       0     0     16
  [14] .fini             PROGBITS         0000000000428928  00028928
       000000000000000d  0000000000000000  AX       0     0     4
  [15] .rodata           PROGBITS         0000000000429000  00029000
       0000000000001180  0000000000000000   A       0     0     16
  [16] .eh_frame_hdr     PROGBITS         000000000042a180  0002a180
       00000000000002ac  0000000000000000   A       0     0     4
  [17] .eh_frame         PROGBITS         000000000042a430  0002a430
       0000000000001780  0000000000000000   A       0     0     8
  [18] .gcc_except_table PROGBITS         000000000042bbb0  0002bbb0
       00000000000005d0  0000000000000000   A       0     0     4
  [19] .init_array       INIT_ARRAY       000000000042dbc8  0002cbc8
       0000000000000010  0000000000000008  WA       0     0     8
  [20] .fini_array       FINI_ARRAY       000000000042dbd8  0002cbd8
       0000000000000008  0000000000000008  WA       0     0     8
  [21] .data.rel.ro      PROGBITS         000000000042dbe0  0002cbe0
       00000000000001f0  0000000000000000  WA       0     0     8
  [22] .dynamic          DYNAMIC          000000000042ddd0  0002cdd0
       0000000000000220  0000000000000010  WA       6     0     8
  [23] .got              PROGBITS         000000000042dff0  0002cff0
       0000000000000010  0000000000000008  WA       0     0     8
  [24] .got.plt          PROGBITS         000000000042e000  0002d000
       0000000000000258  0000000000000008  WA       0     0     8
  [25] .data             PROGBITS         000000000042e258  0002d258
       0000000000000010  0000000000000000  WA       0     0     8
  [26] .bss              NOBITS           000000000042e280  0002d268
       0000000000000180  0000000000000000  WA       0     0     64
  [27] .comment          PROGBITS         0000000000000000  0002d268
       000000000000004a  0000000000000001  MS       0     0     1
  [28] .debug_info       PROGBITS         0000000000000000  0002d2b2
       000000000002a06e  0000000000000000           0     0     1
  [29] .debug_abbrev     PROGBITS         0000000000000000  00057320
       0000000000000a57  0000000000000000           0     0     1
  [30] .debug_line       PROGBITS         0000000000000000  00057d77
       000000000000af9a  0000000000000000           0     0     1
  [31] .debug_str        PROGBITS         0000000000000000  00062d11
       0000000000010328  0000000000000001  MS       0     0     1
  [32] .debug_loc        PROGBITS         0000000000000000  00073039
       0000000000042846  0000000000000000           0     0     1
  [33] .debug_ranges     PROGBITS         0000000000000000  000b587f
       00000000000054c0  0000000000000000           0     0     1
  [34] .symtab           SYMTAB           0000000000000000  000bad40
       00000000000018c0  0000000000000018          35   106     8
  [35] .strtab           STRTAB           0000000000000000  000bc600
       0000000000002177  0000000000000000           0     0     1
  [36] .shstrtab         STRTAB           0000000000000000  000be777
       000000000000016c  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

字段含义

  • Type 字段，具体含义参考文档1-10
  • Link 字段中的值是节头表中节头条目的索引，索引从0开始，表示第一个节头表条目，依此类推。比如5 代表与[ 5] .dynsym 有关

值得注意

One section type, SHT_NOBITS described below, occupies no
space in the file, and its sh_offset member locates the conceptual placement in the
file.

so the number “2d258” remains unchanged.

1
2
3
4
[25] .data             PROGBITS         000000000042e258  0002d258
     0000000000000010  0000000000000000  WA       0     0     8
[26] .bss              NOBITS           000000000042e280  0002d268
     0000000000000180  0000000000000000  WA       0     0     64

.got

global offset table

.plt

This section holds the procedure linkage table. See ‘‘Special Sections’’ in Part 1 and ‘‘Procedure Linkage Table’’ in Part 2 for more information.

Function symbols (those with type STT_FUNC) in shared object files have special significance. When
another object file references a function from a shared object, the link editor automatically creates a procedure linkage table entry for the referenced symbol.

参考文档2-17 page48

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

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

无

Posted Updated operating system41 minutes read (About 6197 words)

Linux Executable file: Structure & Running

可执行文件历史溯源

  • COFF是32位System V平台上使用的一种格式。
    • 它允许使用共享库和调试信息。
    • 然而，它在节的最大数量和节名称的长度限制方面存在缺陷。
    • 它也不能提供C++等语言的符号调试信息。
  • 然而，像XCOFF(AIX)和ECOFF(DEC，SGI)这样的扩展克服了这些弱点，并且有一些版本的Unix使用这些格式。
  • Windows的PE+格式也是基于COFF的。
    可见可执行文件在不同平台上的规则还是有所不同的，后续会以UNIX ELF来分析

ELF 可执行目标文件

exe

可执行目标文件的格式类似于可重定位目标文件的格式。

  1. ELF 头描述文件的总体格式。它还包括程序的入口点（entry point），也就是当程序运行时要执行的第一条指令的地址。
  2. .text、.rodata 和 .data 节与可重定位目标文件中的节是相似的，除了这些节已经被重定位到它们最终的运行时内存地址以外。
  3. .init 节定义了一个小函数，叫做 _init，程序的初始化代码会调用它。
  4. 因为可执行文件是完全链接的（已被重定位），所以它不再需要 .rel 节。

可重定位目标文件

  • 下面内容来自 深入理解计算机系统（CSAPP）的7.4 可重定位目标文件一节
  • 图 7-3 展示了一个典型的 ELF 可重定位目标文件的格式。ELF 可重定位目标文件的格式
  • ELF 头（Executable Linkable Format header）Executable Linkable Format
    • 以一个 16 字节的序列开始，这个序列描述了生成该文件的系统的字的大小和字节顺序。
    • ELF 头剩下的部分包含帮助链接器语法分析和解释目标文件的信息。
      • 其中包括 ELF 头的大小、目标文件的类型（如可重定位、可执行或者共享的）、机器类型（如 X86-64）、节头部表（section header table）的文件偏移，以及节头部表中条目的大小和数量。
  • 节头部表描述不同节的位置和大小，其中目标文件中每个节都有一个固定大小的条目（entry）。

夹在 ELF 头和节头部表之间的都是节。一个典型的 ELF 可重定位目标文件包含下面几个节：

  • .text：已编译程序的机器代码。
    • 通常代码区是可共享的（即另外的执行程序可以调用它），使其可共享的目的是对于频繁被执行的程序，只需要在内存中有一份代码即可。
    • 代码区通常是只读的，使其只读的原因是防止程序意外地修改了它的指令。
  • .rodata：只读数据，比如 printf 语句中的格式串和开关语句的跳转表。
  • .data：已初始化的全局和静态 C 变量。
    • 已经初始化的全局变量、已经初始化?的静态变量（包括全局静态变量和局部静态变量）和常量数据（如字符串常量）。
    • 局部 C 变量在运行时被保存在栈中，既不岀现在 .data 节中，也不岀现在 .bss 节中。
  • .bss：未初始化的全局和静态 C 变量，以及所有被初始化为 0 的全局或静态变量。
    • 在目标文件中这个节不占据实际的空间，它仅仅是一个占位符。
    • 目标文件格式区分已初始化和未初始化变量是为了空间效率：在目标文件中，未初始化变量不需要占据任何实际的磁盘空间。运行时，在内存中分配这些变量，初始值为 0。
      • 用术语 .bss 来表示未初始化的数据是很普遍的。它起始于 IBM 704 汇编语言（大约在 1957 年）中“块存储开始（Block Storage Start）”指令的首字母缩写，并沿用至今。
    • 区分 .data 和 .bss 节的简单方法是把 “bss” 看成是“更好地节省空间（Better Save Space）” 的缩写。
  • .symtab：一个符号表，它存放在程序中定义和引用的函数和全局变量的信息。
    • 一些程序员错误地认为必须通过 -g 选项来编译一个程序，才能得到符号表信息。实际上，每个可重定位目标文件在 .symtab 中都有一张符号表（除非程序员特意用 STRIP 命令去掉它）。
    • 然而，和编译器中的符号表不同，.symtab 符号表不包含局部变量的条目。
  • .rel.text：一个 .text 节中位置的列表，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。
    • 一般而言，任何调用外部函数或者引用全局变量的指令都需要修改。另一方面，调用本地函数的指令则不需要修改。
    • 注意，可执行目标文件中并不需要重定位信息，因此通常省略，除非用户显式地指示链接器包含这些信息。
  • .rel.data：被模块引用或定义的所有全局变量的重定位信息。
    • 一般而言，任何已初始化的全局变量，如果它的初始值是一个全局变量地址或者外部定义函数的地址，都需要被修改。
  • .debug：一个调试符号表，其条目是
    • 程序中定义的局部变量和类型定义，
    • 程序中定义和引用的全局变量，
    • 以及原始的 C 源文件。
    • 只有以 -g 选项调用编译器驱动程序时，才会得到这张表。
  • .line：原始 C 源程序中的行号和 .text 节中机器指令之间的映射。
    • 只有以 -g 选项调用编译器驱动程序时，才会得到这张表。
  • .strtab：一个字符串表，其内容包括 .symtab 和 .debug 节中的符号表，以及节头部中的节名字。字符串表就是以 null 结尾的字符串的序列。

符号和符号表

每个可重定位目标模块 m 都有一个符号表**.symtab**，它包含 m 定义和引用的符号的信息。在链接器的上下文中，有三种不同的符号：

  • (出)由模块 m 定义并能被其他模块引用的全局符号。

    • 全局链接器符号对应于非静态的 C 函数和全局变量。

  • (入)由其他模块定义并被模块 m 引用的全局符号。

    • 这些符号称为外部符号，对应于在其他模块中定义的非静态 C 函数和全局变量。

  • 只被模块 m 定义和引用的局部符号。

    • 对应于带 static 属性的 C 函数和全局变量。这些符号在模块 m 中任何位置都可见，但是不能被其他模块引用。

  • 本地链接器符号和本地程序变量的不同是很重要的。

    • .symtab 中的符号表不包含对应于本地非静态程序变量的任何符号。
    • 这些符号在运行时在栈中被管理，链接器对此类符号不感兴趣。

  • 有趣的是，定义为带有 C static 属性的本地过程变量是不在栈中管理的。

    • 相反，编译器在 .data 或 .bss 中为每个定义分配空间，并在符号表中创建一个有唯一名字的本地链接器符号。

实践：readelf

使用命令readelf -s simple.o 可以读取符号表的内容。

示例程序的可重定位目标文件 main.o 的符号表中的最后三个条目。

  • 开始的 8 个条目没有显示出来，它们是链接器内部使用的局部符号。

  • 全局符号 main 定义的条目，

    • 它是一个位于 .text 节
    • 偏移量为 0（即 value 值）处的 24 字节函数。

  • 其后跟随着的是全局符号 array 的定义

    • 位于 .data 节
    • 偏移量为 0 处的 8 字节目标。

  • 外部符号 sum 的引用。

  • type 通常要么是数据，要么是函数。

    • 符号表还可以包含各个节的条目，以及对应原始源文件的路径名的条目。

  • binding 字段表示符号是本地的还是全局的。

  • Ndx=1 表示 .text 节

    • Ndx=3 表示 .data 节。
    • ABS 代表不该被重定位的符号；
    • UNDEF 代表未定义的符号，也就是在本目标模块中引用，但是却在其他地方定义的符号；

实践: 查看exe信息相关命令



file test

1
2
# read ELF header
readelf -h naive

进一步思考

  • 小结：开辟局部变量、全局变量、malloc空间会影响可执行文件大小吗？对应汇编如何？存放的位置？运行时如何？

    • 设计一个代码量小但是占空间很大的可执行文件。
      • 因为已经初始化的全局变量、已经初始化的静态变量（包括全局静态变量和局部静态变量）会存储在data段，所以这些变量的大小会影响可执行文件的大小。

    • static 与 const效果一样。
    • 设计一个代码量小但是运行时占内存空间很大的可执行文件。
      • malloc的空间会影响运行时的内存空间，但是不会影响可执行文件的大小。

  • 将exe各节内容可视化解释(虽然现在是二进制)

  • 编译的时候，头文件是怎么处理的？

  • data 与 bbs在存储时怎么区分全局与静态变量

    • 符号表为什么有全局变量的符号，这些静态局部变量不需要吗？应该是需要的

  • 请给出 .rel.text .rel.data的实例分析

线程与进程

  • 调度：进程是资源管理的基本单位，线程是程序执行的基本单位。
  • 切换：线程上下文切换比进程上下文切换要快得多。
    • TLB是每个核私有的，如果一个核从一个进程切换到另一个进程，TLB要全部清空。
    • 但是线程不需要，因为线程共享相同的虚拟地址空间。
    • 所以线程切换开销远小于进程切换开销。
  • 拥有资源： 进程是拥有资源的一个独立单位，线程不拥有系统资源，但是可以访问隶属于进程的资源。
  • 系统开销： 创建或撤销进程时，系统都要为之分配或回收系统资源，如内存空间，I/O设备等，OS所付出的开销显著大于在创建或撤销线程时的开销，进程切换的开销也远大于线程切换的开销。

（软件）多线程与（CPU）超线程

线程和进程都可以用多核，但是线程共享进程内存（比如，openmp）

超线程注意也是为了提高核心的利用率，当有些轻量级的任务时（读写任务）核心占用很少，可以利用超线程把一个物理核心当作多个逻辑核心，一般是两个，来使用更多线程。AMD曾经尝试过4个。

单核多进程切换

进程结构

正在运行的程序，叫进程。每个进程都有完全属于自己的，独立的，不被干扰的内存空间。此空间，被分成几个段(Segment),分别是Text, Data, BSS, Heap, Stack。

esp ebp

  • push pop %ebp 涉及到编译器调用函数的处理方式 application binary interface (ABI).
  • 如何保存和恢复寄存器
    • 比如：cdecl（代表 C 声明）是 C 编程语言的调用约定，被许多 C 编译器用于 x86 体系结构。 在 cdecl 中，子例程参数在堆栈上传递。整数值和内存地址在 EAX 寄存器中返回，浮点值在 ST0 x87 寄存器中返回。寄存器 EAX、ECX 和 EDX 由调用方保存，其余寄存器由被叫方保存。x87 浮点寄存器 调用新函数时，ST0 到 ST7 必须为空（弹出或释放），退出函数时ST1 到 ST7 必须为空。ST0 在未用于返回值时也必须为空。

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
0000822c <func>:
    822c: e52db004  push {fp}  ; (str fp, [sp, #-4]!) 如果嵌套调用 push {fp,lr}
    8230: e28db000  add fp, sp, #0
    8234: e24dd014  sub sp, sp, #20
    8238: e50b0010  str r0, [fp, #-16]
    823c: e3a03002  mov r3, #2
    8240: e50b3008  str r3, [fp, #-8]
    8244: e51b3008  ldr r3, [fp, #-8]
    8248: e51b2010  ldr r2, [fp, #-16]
    824c: e0030392  mul r3, r2, r3
    8250: e1a00003  mov r0, r3
    8254: e24bd000  sub sp, fp, #0
    8258: e49db004  pop {fp}  ; (ldr fp, [sp], #4) 如果嵌套调用 pop {fp,lr}
    825c: e12fff1e  bx lr          ; MOV PC,LR

00008260 <main>:
    8260: e92d4800  push {fp, lr}
    8264: e28db004  add fp, sp, #4
    8268: e24dd008  sub sp, sp, #8
    826c: e3a03019  mov r3, #25
    8270: e50b3008  str r3, [fp, #-8]
    8274: e51b0008  ldr r0, [fp, #-8]
    8278: ebffffeb  bl 822c <func>
    827c: e3a03000  mov r3, #0
    8280: e1a00003  mov r0, r3
    8284: e24bd004  sub sp, fp, #4
    8288: e8bd8800  pop {fp, pc}

arm PC = x86 EIP
ARM 为什么这么设计，就是为了返回地址不存栈，而是存在寄存器里。但是面对嵌套的时候，还是需要压栈。

栈区（stack）

由编译器自动分配释放，存放函数的参数值、返回值、局部变量等。在程序运行过程中实时加载和释放，因此，局部变量的生存周期为申请到释放该段栈空间。

WIndow系统一般是2MB。Linux可以查看ulimit -s ，通常是8M

栈空间最好保持在cache里，太大会存入内存。持续地重用栈空间有助于使活跃的栈内存保持在CPU缓存中，从而加速访问。进程中的每个线程都有属于自己的栈。向栈中不断压入数据时，若超出其容量就会耗尽栈对应的内存区域，从而触发一个页错误。

函数参数传递一般通过寄存器，太多了就存入栈内。

大数组seg fault

栈区(stack segment)：由编译器自动分配释放，存放函数的参数的值，局部变量的值等。

局部变量空间是很小的，我们开一个a[1000000]就会导致栈溢出；而全局变量空间在Win 32bit 下可以达到4GB，因此不会溢出。

或者malloc使用堆的区域，但是记得free。

堆区（heap）

用于动态内存分配。堆在内存中位于BSS区和栈区之间。一般由程序员分配和释放，若程序员不释放，程序结束时有可能由OS回收。

分配的堆内存是经过字节对齐的空间，以适合原子操作。堆管理器通过链表管理每个申请的内存，由于堆申请和释放是无序的，最终会产生内存碎片。堆内存一般由应用程序分配释放，回收的内存可供重新使用。若程序员不释放，程序结束时操作系统可能会自动回收。

用户堆，每个进程有一个，进程中的每个线程都从这个堆申请内存，这个堆在用户空间。所谓内训耗光，一般就是这个用户堆申请不到内存了，申请不到分两种情况，一种是你 malloc 的比剩余的总数还大，这个是肯定不会给你了。第二种是剩余的还有，但是都不连续，最大的一块都没有你 malloc 的大，也不会给你。解决办法，直接申请一块儿大内存，自己管理。

除非特殊设计，一般你申请的内存首地址都是偶地址，也就是说你向堆申请一个字节，堆也会给你至少4个字节或者8个字节。

堆有一个堆指针（break brk），也是按照栈的方式运行的。内存映射段是存在在break brk指针与esp指针之间的一段空间。

在Linux中当动态分配内存大于128K时，会调用mmap函数在esp到break brk之间找一块相应大小的区域作为内存映射段返回给用户。

当小于128K时，才会调用brk或者sbrk函数，将break brk向上增长（break brk指针向高地址移动）相应大小，增长出来的区域便作为内存返回给用户。

两者的区别是

内存映射段销毁时，会释放其映射到的物理内存，

而break brk指向的数据被销毁时，不释放其物理内存，只是简单将break brk回撤，其虚拟地址到物理地址的映射依旧存在，这样使的当再需要分配小额内存时，只需要增加break brk的值，由于这段虚拟地址与物理地址的映射还存在，于是不会触发缺页中断。只有在break brk减少足够多，占据物理内存的空闲虚拟内存足够多时，才会真正释放它们。

栈堆的区别

  1. 产生碎片不同
    对堆来说，频繁的new/delete或者malloc/free势必会造成内存空间的不连续，造成大量的碎片，使程序效率降低。

对栈而言，则不存在碎片问题，因为栈是先进后出的队列，永远不可能有一个内存块从栈中间弹出。

设计考虑

  1. 代码段和数据段分开，运行时便于分开加载，在哈佛体系结构的处理器将取得更好得流水线效率。
  2. 代码时依次执行的，是由处理器 PC 指针依次读入，而且代码可以被多个程序共享，数据在整个运行过程中有可能多次被调用，如果将代码和数据混合在一起将造成空间的浪费。
  3. 临时数据以及需要再次使用的代码在运行时放入栈中，生命周期短，便于提高资源利用率。
  4. 堆区可以由程序员分配和释放，以便用户自由分配，提高程序的灵活性。

缓冲区溢出攻击（代码注入攻击

  • 缓冲区溢出（Buffer Overflow）是一种常见的软件漏洞，它发生在程序中使用缓冲区（一块内存区域）来存储数据时，输入的数据超过了缓冲区的容量，导致多余的数据溢出到相邻的内存区域。
    • 常见栈上分配空间，然后溢出直接覆盖前面的返回地址，使得返回到任意代码片段执行。如果开启了栈上执行代码，甚至能栈上注入代码并执行。

虚拟内存

用户进程内存空间，也是系统内核分配给该进程的VM(虚拟内存)，但并不表示这个进程占用了这么多的RAM(物理内存)。这个空间有多大？命令top输出的VIRT值告诉了我们各个进程内存空间的大小（进程内存空间随着程序的执行会增大或者缩小）。

Linux虚拟地址空间分布

虚拟地址空间在32位模式下它是一个4GB的内存地址块。在Linux系统中, 内核进程和用户进程所占的虚拟内存比例是1:3,如下图。而Windows系统为2:2(通过设置Large-Address-Aware Executables标志也可为1:3)。这并不意味着内核使用那么多物理内存，仅表示它可支配这部分地址空间，根据需要将其映射到物理内存。

值得注意的是，每个进程的内核虚拟地址空间都是映射到相同的真实物理地址上，因为都是共享同一份物理内存上的内核代码。除此之外还要注意内核虚拟地址空间总是存放在虚拟内存的地址最高处。

其中，用户地址空间中的蓝色条带对应于映射到物理内存的不同内存段，灰白区域表示未映射的部分。这些段只是简单的内存地址范围，与Intel处理器的段没有关系。

上图中Random stack offset和Random mmap offset等随机值意在防止恶意程序。Linux通过对栈、内存映射段、堆的起始地址加上随机偏移量来打乱布局，以免恶意程序通过计算访问栈、库函数等地址。

execve(2)负责为进程代码段和数据段建立映射，真正将代码段和数据段的内容读入内存是由系统的缺页异常处理程序按需完成的。另外，execve(2)还会将BSS段清零。

top

VIRT = SWAP + RES # 总虚拟内存=动态 + 静态

RES >= CODE + DATA + SHR. # 静态内存 = 代码段 + 静态数据段 + 共享内存

MEM = RES / RAM

1
2
3
4
5
6
7
                          DATA CODE  RES VIRT
before allocation:         124    4  408 3628
after 5MB allocation:     5008    4  476 8512           //malloc 5M, DATA和VIRT增加5M, RES不变
after 2MB initialization: 5008    4 2432 8512           //初始化 2M, DATA和VIRT不变， RES增加2M


//如果最后加上free(data),  DATA, RES, VIRT又都会相应的减少，回到最初的状态

top 里按f 可以选择要显示的内容。

SWAP

  • Swapping的大部分时间花在数据传输上，交换的数据也越多，意味时间开销也随之增加。对于进程而言，这个过程是透明的。
    • so(swap out)：由于RAM资源不足，PFRA会将部分匿名页框的数据写入到交换区(swap area)，备份之。
    • si(swap in) : 当发生内存缺页异常的时候，缺页异常处理程序会将交换区(磁盘)的页面又读回物理内存。
  • 每次Swapping，都有可能不只是一页数据，不管是si，还是so。Swapping意味着磁盘操作，更新页表等操作，这些操作开销都不小，会阻塞用户态进程。所以，持续飚高的si/so意味着物理内存资源是性能瓶颈。
  • 在内存空间设计早期只有分段没有分页时，SWAP还可以用来内存交换(暂存内存数据，重新排列内存)，来消除内存碎片。

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

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

https://blog.csdn.net/zy986718042/article/details/73556012

https://blog.csdn.net/qq_38769551/article/details/103099014

https://blog.csdn.net/ywcpig/article/details/52303745

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

https://www.bilibili.com/video/BV1N3411y7Mr?spm_id_from=444.41.0.0

Posted Updated Programming6 minutes read (About 874 words)

PythonRegex

pattern

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
^	匹配字符串的开头
$	匹配字符串的末尾。
.	匹配任意字符，除了换行符
a| b	匹配a或b
[a-zA-Z0-9]	匹配任何字母及数字
\d	匹配数字。等价于[0-9]。
[aeiou]	匹配中括号内的任意一个字母
[^aeiou]	除了aeiou字母以外的所有字符
\w	匹配包括下划线的任何单词字符。等价于'[A-Za-z0-9_]'。
(\s*) 或者 ([\t ]*)     来匹配任意TAB和空格的混合字符

\s	匹配任何空白字符，包括空格、制表符、换页符等等。等价于 [ \f\n\r\t\v]。
\S	匹配任何非空白字符。等价于 [^ \f\n\r\t\v]。
\b	匹配一个单词边界，也就是指单词和空格间的位置。例如， 'er\b' 可以匹配"never" 中的 'er'，但不能匹配 "verb" 中的 'er'。
\B	匹配非单词边界。'er\B' 能匹配 "verb" 中的 'er'，但不能匹配 "never" 中的 'er'。

重复

1
2
3
4
5
6
7
8
9
10
11
12
re*	匹配0个或多个的表达式。
re+	匹配1个或多个的表达式。
re?	匹配0个或1个由前面的正则表达式定义的片段，非贪婪方式
re{ n}	精确匹配 n 个前面表达式。
        例如， o{2} 不能匹配 "Bob" 中的 "o"，
        但是能匹配 "food" 中的两个 o。
re{ n,}	匹配 n 个前面表达式。
        例如， o{2,} 不能匹配"Bob"中的"o"，
        但能匹配 "foooood"中的所有 o。
        "o{1,}" 等价于 "o+"。
        "o{0,}" 则等价于 "o*"。
re{ n, m}	匹配 n 到 m 次由前面的正则表达式定义的片段，贪婪方式

match exactlly str

1
2
3
4
5
6
7
# find should use \ to represent the (6|12|3)
$ find ~/github/gapbs/ -type f -regex '.*/kron-\(6\|12\|3\).*'
/staff/shaojiemike/github/gapbs/kron-12.wsg
/staff/shaojiemike/github/gapbs/kron-3.sg
/staff/shaojiemike/github/gapbs/kron-3.wsg
/staff/shaojiemike/github/gapbs/kron-6.sg
/staff/shaojiemike/github/gapbs/kron-6.wsg

re.match与re.search的区别

re.match只匹配字符串的开始，如果字符串开始不符合正则表达式，则匹配失败，函数返回None；

而re.search匹配整个字符串，直到找到一个匹配。

re.match函数

从字符串的起始位置匹配

1
re.match(pattern, string, flags=0)

flags

多个标志可以通过按位 OR(|) 它们来指定。如 re.I | re.M被设置成 I 和 M 标志：

1
2
3
re.I	使匹配对大小写不敏感
re.M	多行匹配，影响 ^ 和 $
re.S	使 . 匹配包括换行在内的所有字符

group

1
2
3
4
5
6
7
8
matchObj = re.match( r'(.*) are (.*?) .*', line, re.M|re.I)
 
if matchObj:
   print "matchObj.group() : ", matchObj.group()
   print "matchObj.group(1) : ", matchObj.group(1)
   print "matchObj.group(2) : ", matchObj.group(2)
else:
   print "No match!!"

打印部分内容

1
2
3
matchObj.group() :  Cats are smarter than dogs
matchObj.group(1) :  Cats
matchObj.group(2) :  smarter

re.sub 替换

findall

返回元组，可以指定开始，与结束位置。

1
2
3
result = re.findall(r'(\w+)=(\d+)', 'set width=20 and height=10')
print(result)
# [('width', '20'), ('height', '10')]

实例：objdump结果只提取汇编的命令

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

import re      
# 打开x86汇编代码文件
with open(assembly) as f:
        # 读取文件内容
        content = f.read()

# 使用正则表达式匹配所有汇编指令，
pattern = r'\b([a-zA-Z]{3,6})\b.*'
# 匹配pattern，但是只将()内结果保存在matches中
matches = re.findall(pattern, content)

# 输出匹配结果
for match in matches:
        print(match)

re.split

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

https://blog.csdn.net/weixin_39594191/article/details/111611346

https://www.runoob.com/python/python-reg-expressions.html

Posted Updated Operating system8 minutes read (About 1143 words)

Library GLIBC

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
  1. 使用ldconfig命令查找：ldconfig是Linux系统中用于配置动态链接器的命令。您可以运行以下命令来查找libstdc++库的路径：
1
ldconfig -p | grep libstdc++.so
  1. 在默认路径下查找：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，没有进行正确性的交叉校验。

无

Posted Updated Architecture15 minutes read (About 2206 words)

llvm

llvm

LLVM项目开始于一种比Java字节码更低层级的IR，因此，初始的首字母缩略词是Low Level Virtual Machine。它的想法是发掘低层优化的机会，采用链接时优化。

插一嘴：链接时优化

  • GCC也支持链接时优化，称为LTO（Link Time Optimization），通过把多个编译单元中分别生成的目标文件在链接时进行全局的优化，可以提高程序的执行效率。
  • 具体内容：大幅度减少可执行文件的体积
    • 冗余代码和变量/函数的消除：对于在多个模块中出现的相同代码/变量/函数，链接时优化可以将它们合并，从而减少可执行文件的体积，提高程序的执行效率。
    • 内联函数：将函数调用直接替换为函数本身的代码，从而减少函数调用的开销，提高程序的执行效率。
    • 循环展开和向量化：内联函数后，或许能进一步将循环展开和向量化，从而减少循环体内的分支判断，优化程序的执行效率。

IR：gcc与llvm的区别

学过编译原理的人都知道，编译过程主要可以划分为前端与后端：

  • 前端把源代码翻译成中间表示 (IR)。
  • 后端把IR编译成目标平台的机器码。当然，IR也可以给解释器解释执行。

经典的编译器如gcc：在设计上前端到后端编写是强耦合的，你不需要知道，无法知道，也没有API来操作它的IR。

  • 好处是：因为不需要暴露中间过程的接口，编译器可以在内部做任何想做的平台相关的优化。

  • 坏处是，每当一个新的平台出现，这些编译器都要各自为政实现一个从自己的IR到新平台的后端。

    • 甚至如果当一种新语言出现，且需要实现一个新的编译器，那么可能需要设计一个新的IR，以及针对大部分平台实现这个IR的后端。
    • 如果有M种语言、N种目标平台，那么最坏情况下要实现 M*N 个前后端。这是很低效的。

  • LLVM的核心设计了一个叫 LLVM IR 的通用中间表示， 并以库(Library) 的方式提供一系列接口， 为你提供诸如操作IR、生成目标平台代码等等后端的功能。

  • 在使用通用IR的情况下，如果有M种语言、N种目标平台，那么最优情况下我们只要实现 M+N 个前后端。

llvm IR

  • LLVM IR 中间表示是适用于多种编程语言的通用中间表示，支持C、C++、Objective-C、Swift、Java、Python等多种编程语言。
  • 它是一种低级别的语言，类似于汇编语言，但比汇编语言更高级，包含了类型、变量、函数、控制流等高级语言的特性。
  • LLVM编译器可以将多种编程语言编译成LLVM IR，从而可以在LLVM IR层面进行各种优化处理，再将LLVM IR转换为目标平台的机器码。
    • 比如要将Python脚本编译成LLVM IR中间表示，可以使用Python LLVM编译器llvmlite和numba。

LLVM IR表示与转换

LVM IR实际上有三种表示：

  • .ll 格式：人类可以阅读的文本。
  • .bc 格式：适合机器存储的二进制文件。
  • 内存表示

各种格式是如何生成并相互转换：

格式 转换命令
.c -> .ll clang -emit-llvm -S a.c -o a.ll
.c -> .bc clang -emit-llvm -c a.c -o a.bc
.ll -> .bc llvm-as a.ll -o a.bc
.bc -> .ll llvm-dis a.bc -o a.ll
.bc -> .s llc a.bc -o a.s

对于LLVM IR来说，.ll文件就相当于汇编，.bc文件就相当于机器码。 这也是llvm-as和llvm-dis指令为什么叫as和dis的缘故。

llvm 前端

前端

clang实现的前端包括

  • 词法分析(识别标记)
    • 处理源代码的文本输入，将语言结构分解为一组单词和标记，去除注释、空白、制表符等。每个单词或者标记必须属于语言子集，语言的保留字被变换为编译器内部表示。
    • 词法分析报错的例子包括：拼写错误、注释没有正确结束、字符串没有正确结束等。
  • 语法分析(标记结构完整)
    • 语法分析器会根据语法规则验证程序的正确性，如缺少右括号、是否缺少关键字、变量未定义、函数应该有返回值等。
  • 语义分析(有无语义矛盾)
    • 借助符号表检验代码没有违背语言类型系统。这个表存储标识符（符号）和它们各自的类型之间的映射，以及其它内容。
    • 类型检查的一种直觉的方法是，在解析之后，遍历AST的同时从符号表收集关于类型的信息。
    • 例子：定义了两个变量 a 冲突。

llvm 后端

见 llvm Backend 一文

clang

clang 与 llvm的关系

Clang 是 LLVM 项目中的一个 C/C++/Objective-C 编译器，它使用 LLVM 的前端和后端进行代码生成和优化。它可以将 C/C++/Objective-C 代码编译为 LLVM 的中间表示（LLVM IR），然后进一步将其转换为目标平台的机器码。Clang 拥有很好的错误信息展示和提示，支持多平台使用，是许多开发者的首选编译器之一。同时，Clang 也作为 LLVM 项目的一个前端，为 LLVM 的生态系统提供了广泛的支持和应用。

clang 的开发与苹果公司的关系

Clang 的开发起源于苹果公司的一个项目，即 LLVM/Clang 项目。在 2005 年，苹果公司希望能够使用一种更加灵活、可扩展、优化的编译器来替代 GCC 作为其操作系统 macOS (Mac OS X) 开发环境的默认编译器。由于当时的 GCC 开发被其维护者们认为变得缓慢和难以维护，苹果公司决定开发一款新的编译器，这就是 Clang 诞生的原因。Clang 的开发团队由该项目的创立者 Chris Lattner 领导，他带领团队将 Clang 发展为一款可扩展、模块化、高效的编译器，并成功地将其嵌入到苹果公司的开发工具链 Xcode 中，成为了 macOS 开发环境中默认的编译器之一。

Clang 是一个开源项目，在苹果公司的支持下，Clang 的开发得到了全球各地的开发者们的广泛参与和贡献。现在，Clang 成为了 LLVM 生态中的一个重要组成部分，被广泛地应用于多平台的编译器开发中。

clang-cannot-find-iostream

Clang and Clang++ “borrow” the header files from GCC & G++. It looks for the directories these usually live in and picks the latest one. If you’ve installed a later GCC without the corresponding G++, Clang++ gets confused and can’t find header files. In your instance, for example, if you’ve installed gcc 11 or 12.

You can use clang-10 -v -E or clang++-10 -v -E to get details on what versions of header files it’s trying to use.

安装g++-12解决

常用工具

github/tools目录下有许多实用工具

  • llvm-as：把LLVM IR从人类能看懂的文本格式汇编成二进制格式。注意：此处得到的不是目标平台的机器码。
  • llvm-dis：llvm-as的逆过程，即反汇编。 不过这里的反汇编的对象是LLVM IR的二进制格式，而不是机器码。
  • opt：优化LLVM IR。输出新的LLVM IR。
  • llc：把LLVM IR编译成汇编码。需要用as进一步得到机器码。
  • lli：解释执行LLVM IR。

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

文章部分内容来自ChatGPT-3.5，暂时没有校验其可靠性(看上去貌似说得通)。

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

Posted Updated Algorithms15 minutes read (About 2268 words)

Dynamic Programming

动态规划简介

将一件事情分成若干阶段，然后通过阶段之间的转移达到目标。由于转移的方向通常是多个，因此这个时候就需要决策选择具体哪一个转移方向。

动态规划所要解决的事情通常是完成一个具体的目标，而这个目标往往是最优解。并且：

  1. 阶段之间可以进行转移，这叫做动态。
  2. 达到一个可行解(目标阶段) 需要不断地转移，那如何转移才能达到最优解？这叫规划。

每个阶段抽象为状态（用圆圈来表示），状态之间可能会发生转化（用箭头表示）。可以画出类似如下的图：

性质：

  1. 最优子结构
    1. 问题的最优解所包含的子问题的解也是最优的
    2. 注意： 具有最优子结构也可能是适合用贪心的方法求解。
  2. 无后效性
    1. 已经求解的子问题，不会再受到后续(父问题)决策的影响。
    2. 即子问题的解一旦确定，就不再改变，不受在这之后、包含它的问题的求解决策的影响。
  3. 子问题重叠
    1. 如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

基本思路

对于一个能用动态规划解决的问题，一般采用如下思路解决：

  • 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
  • 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
  • 按顺序求解每一个阶段的问题。
    如果用图论的思想理解，我们建立一个 有向无环图，每个状态对应图上一个节点，决策对应节点间的连边。

难点，重点

如何找到转移关系：

  1. 可以伸缩的维度： 一般是数组的下标，或者是字符串的下标，或者是树的节点。也可以是问题的query数值。
  2. 分情况讨论的，最大值为不同情况的最大值。方案数为所有情况的总和。

DP分类

  • 背包DP

    • 0-1背包
      • 定义：每个物体只有两种可能的状态（取与不取），对应二进制中的 0 和 1，这类问题便被称为「0-1 背包问题」
        • 一般有个总cost为W来限制选择
      • 基础版：可以通过滚动数组减少空间占用，但是注意遍历方向
      • 常见变形：
        • 至多装capacity,求方案数/最大价值和
        • 恰好装capacity,求方案数/最大/最小价值和
          • 方案数，将转移公式最大值，改成加法。注意会多一维度数据。基础1+提升2
        • 至少装capacity,求方案数/最小价值和
      • 变种：总cost等于W时，和为half的子集是否存在
        • 方法一：
          • 背包的体积为sum / 2
          • 每个物品 cost = value
          • 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
        • 方法二：
          • 状态：前i个元素，和为j的子集是否存在
          • 转移关系: \( f(i,j)=(f(i-1,j)+f(i-1,j-a[i])>0)?1:0 \) 注意： f[i,0]=1
      • 变种：选择和为k的子集的
      • 变种2：总cost等于W时，和为half的子集的个数 题目：2022.9.23-求和
        • 状态：前i个元素，和为j的子集个数
        • 转移关系: \( f(i,j)=f(i-1,j)+f(i-1,j-a[i]) \) 注意： f[i,0]=1
    • 完全背包: 每个物体可以选择多次
      • 转移关系: 也可以由f(i, j-w)转移到f(i,j)
    • 多重背包: 每个物体可以选择\( k_i \)次
      • 朴素思路: 每步可以总\( k_i \)里选最大, \( f_{i,j} = max_{k=0}^{k_i}(f_{i-1,j - k \times w_{i}} + v_{i} \times k ) \)
      • 二进制分组优化
        • 思想：多重背包，其实是有很多重复元素的0-1背包，通过二进制来唯一表示选取，来最小0-1背包的可选物品数
        • 具体操作: 方法是：将第 i 种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为\( 1,2,4,\ldots,2^{k-1},n-2^k+1 \)，且 k 是满足\( n[i]-2^k+1>0 \)的最大整数。例如，如果 n[i] 为 13，就将这种物品分成系数分别为 1, 2, 4, 6 的 4 件物品。
        • 效果：将第 i 种物品分成了 O(log⁡n[i]) 种物品，将原问题\( O(V\times\sum n[i]) \)转化为了复杂度为\( O(V\times\sum \log n[i]) \)的 01 背包问题
          1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          13
          14
          15
          16
          17
          18
          19
          20
          21
          int num[maxn][2], dp[maxn];
          int N, V, c, w, n, tot;
          memset(dp, 0, sizeof dp);
          cin >> V >> N; tot = 1;
          for(int i = 1; i <= N; ++i)
          {
            cin >> c >> w >> n; // 第 i 物品的费用、价值和数量
            for(int k = 1; k < n; k<<=1)//左移求下一个所需二进制数 
            {
              num[tot][0] = k*c; // 添加 子物品
              num[tot++][1] = k*w;
              n -= k;
            }
            num[tot][0] = n*c; // 添加n[i]-2^k+1的 子物品
            num[tot++][1] = n*w;
          }
          for(int i = 1; i < tot; ++i)
          {
            for(int j = V; j >= num[i][0]; --j) // 0-1 背包 滚动数组实现
              dp[j] = max(dp[j], dp[j-num[i][0]]+num[i][1]);
          }
      • 单调队列优化 to finish

  • 区间DP

    • \( f(i,j)=max_k{f(i,k)+f(k+1,j)+cost} \)

  • DAG 上的DP

    • DAG(Directed Acyclic Graph) 即 有向无环图，一些实际问题中的二元关系都可使用 DAG 来建模，从而将这些问题转化为 DAG 上的最长（短）路问题。
    • to do

  • 树形 DP 往往需要递归DFS

    • 分阶段参数：当前子树的根节点
    • 转移关系：当前子树的根节点和其子节点的关系
    • 例题： to do

记忆化搜索

  • 子问题间重叠的部分会有很多，同一个子问题可能会被重复访问多次，效率还是不高。
  • 思路: 记忆化，参数一定，那么返回值也一定不会变，因此下次如果碰到相同的参数，我们就可以将上次计算过的值直接返回，而不必重新计算。这样节省的时间就等价于去除的重叠子问题的耗时。
  • 解决方法：把每个子问题的解存储下来，通过记忆化的方式，确保每个子问题只被计算一次。

如何写记忆化搜索

  • 方法一
    • 把这道题的 dp 状态和方程写出来
    • 根据它们写出 dfs 函数
    • 添加记忆化数组
  • 方法二
    • 写出这道题的暴搜程序（最好是 dfs)
    • 将这个 dfs 改成「无需外部变量」的 dfs
    • 添加记忆化数组

实例：朴素DFS递归，实现记忆化

爬楼梯问题的暴力普通递归DFS代码

1
2
3
4
5
function climbStairs(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

添加与DFS参数相关的记忆化数组，将这个 dfs 改成「无需外部变量」的 dfs。

1
2
3
4
5
6
7
8
9
memo = {}
def climbStairs(n):
  if n == 1:return 1
  if n == 2: return 2
  if n in memo: return memo[n]
  ans = func(n - 1) + func(n-2)
  memo[n] = ans
  return ans
climbStairs(10)

优化技巧

状态压缩 & 动态规划

状压+动态规划(DP, Dynamic Programming)

使用的数有限（共 10 个），并且使用到的数最多出现一次，容易想到使用「状压 DP」来求解：我们使用一个二进制数来表示具体的子集具体方案。

定义 f[state] 为当前子集选择数的状态为 state 时的方案数，state 为一个长度 10 的二进制数，若 state 中的第 k 位二进制表示为 1，代表数值 p[k] 在好子集中出现过；若第 k 位二进制表示为 0 代表 p[k] 在好子集中没出现过。

状态压缩

状态压缩有关，比如用 4 个字节存储状态

需要进一步的研究学习

动态规划 与 np完全的关系

遇到的问题

暂无

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

参考文献

视频： https://www.bilibili.com/video/BV1Xj411K7oF/?vd_source=5bbdecb1838c6f684e0b823d0d4f6db3

https://oi-wiki.org/dp/basic/

https://www.zhihu.com/question/316416327/answer/626807333

Posted Updated Programming13 minutes read (About 1897 words)

Python Class

简介

Python从设计之初就已经是一门面向对象的语言，正因为如此，在Python中创建一个类和对象是很容易的。

面向对象技术简介

  • 类(Class): 用来描述具有相同的属性和方法的对象的集合。它定义了该集合中每个对象所共有的属性和方法。对象是类的实例。

  • 实例化：创建一个类的实例，类的具体对象。

  • 方法：类中定义的函数。

    • 方法重写：如果从父类继承的方法不能满足子类的需求，可以对其进行改写，这个过程叫方法的覆盖（override），也称为方法的重写。
    • 继承：即一个派生类（derived class）继承基类（base class）的字段和方法。继承也允许把一个派生类的对象作为一个基类对象对待。例如，有这样一个设计：一个Dog类型的对象派生自Animal类，这是模拟”是一个（is-a）”关系（例图，Dog是一个Animal）。

  • 对象：通过类定义的数据结构实例。对象包括两个数据成员（类变量和实例变量）和方法。

    • 类变量：类变量在整个实例化的对象中是公用的。类变量定义在类中且在函数体之外。类变量通常不作为实例变量使用。
    • 实例变量：在类的声明中，属性是用变量来表示的。这种变量就称为实例变量，是在类声明的内部但是在类的其他成员方法之外声明的。

何时使用类

  1. 数据与操作紧密相关
  2. 对象有许多状态需要维护,可以使用类中的属性来保存状态。
  3. 需要生成多个仅在部分属性不同的实例,可以使用类作为模板。
  4. 不同对象存在公共parent-child的层次关系,可以使用继承来复用代码。
  5. 隐藏对象的实现细节,只对外公开接口。

类变量 与 实例变量

在Python中,类变量和实例变量是两个不同的概念:

  1. 类变量(Class Variable)
  • 定义在类内部,但不在任何方法之内
  • 被该类的所有实例对象所共享
  • 可以通过类名或实例对象访问
  • 用于定义与这个类相关的特征或属性
  1. 实例变量(Instance Variable)
  • 定义在类内部的方法之内
  • 每个实例对象拥有属于自己的变量副本
  • 只能通过实例对象访问
  • 用于定义实例对象的个性化特征或状态

例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Person:

    species = 'Human' # 类变量

    def __init__(self, name):
        self.name = name # 实例变量

p1 = Person('John')
p2 = Person('Mary')

print(p1.species) # Human
print(p2.species) # Human 

print(p1.name) # John 
print(p2.name) # Mary

综上,类变量用于定义类的通用属性,实例变量用于定义实例的独特属性。区分二者是理解Python面向对象的关键。

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Employee:
   '所有员工的基类'
   empCount = 0 # 类变量
 
   def __init__(self, name, salary):
      self.name = name
      self.salary = salary
      Employee.empCount += 1
   
   def displayCount(self):
     print "Total Employee %d" % Employee.empCount
 
   def displayEmployee(self):
      print "Name : ", self.name,  ", Salary: ", self.salary

类函数必有参数 ‘self’

必须有一个额外的第一个参数名称, 按照惯例它的名称是 self，self 不是 python 关键字，换成其他词语也行。

创建实例对象与访问

1
2
emp1 = Employee("Zara", 2000)
emp1.displayEmployee()

继承

通过继承创建的新类称为子类或派生类，被继承的类称为基类、父类或超类。

继承语法 class 派生类名(基类名)

调用基类

调用基类的方法时，需要加上基类的类名前缀，且需要带上 self 参数变量。区别在于类中调用普通函数时并不需要带上 self 参数
,这点在代码上的区别如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Base:
    def base_method(self):
        print("Base method")

class Derived(Base):
    def derived_method(self):
        # 调用基类方法要加类名前缀
        Base.base_method(self)
        
        # 调用普通函数
        print("Hello")  
        
d = Derived()
d.derived_method()

# 输出
Base method  
Hello

在Derived类中:

  • 调用Base基类的方法base_method(),需要写成Base.base_method(self)

  • 调用普通函数print(),直接写函数名即可

区别在于:

  • 调用基类方法需要指明方法所属的基类
  • 基类方法需要传入self,指代实例自己

而对于普通函数,只需要直接调用即可,不需要self参数。

这与Python的名称空间和面向对象实现有关,是理解Python类继承的关键点。

运算符重载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
__init__ : 构造函数，在生成对象时调用
__del__ : 析构函数，释放对象时使用
__repr__ : 打印，转换
__setitem__ : 按照索引赋值
__getitem__: 按照索引获取值
__len__: 获得长度
__cmp__: 比较运算
__call__: 函数调用
__add__: 加运算
__sub__: 减运算
__mul__: 乘运算
__truediv__: 除运算
__mod__: 求余运算
__pow__: 乘方

PyTorch 中如果继承torch.nn.Module，执行__call__会转接到forward方法

torch.nn.Module 的 __call__ 方法会调用 forward 方法，并且在调用 forward 之前和之后还会执行一些其他的操作，比如设置钩子（hooks）和调用 _check_forward_hooks 等。

以下是 torch.nn.Module 中 __call__ 方法的简化实现逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Module:
    def __call__(self, *input, **kwargs):
        # 在调用 forward 之前执行一些操作
        # 例如，调用 forward pre-hooks
        for hook in self._forward_pre_hooks.values():
            result = hook(self, input)
            if result is not None:
                if not isinstance(result, tuple):
                    result = (result,)
                input = result

        # 调用 forward 方法
        result = self.forward(*input, **kwargs)

        # 在调用 forward 之后执行一些操作
        # 例如，调用 forward hooks
        for hook in self._forward_hooks.values():
            hook_result = hook(self, input, result)
            if hook_result is not None:
                result = hook_result

        return result
  1. __call__ 方法：当你实例化一个 Module 并调用它时（例如 model(input)），Python 会调用 __call__ 方法。
  2. forward 方法：__call__ 方法内部会调用 forward 方法，这是你需要在子类中重写的方法，用于定义前向传播的逻辑。
  3. 钩子（Hooks）：在调用 forward 之前和之后，__call__ 方法会处理一些钩子。这些钩子可以用于调试、可视化或其他目的。

+=

在Python中可以通过特殊方法__iadd__来对+=符号进行重载。

__iadd__需要定义在类中,用于指定+=操作时的具体行为。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Vector:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __iadd__(self, other):
        self.x += other.x
        self.y += other.y
        return self

v1 = Vector(1, 2)
v2 = Vector(3, 4)

v1 += v2
print(v1.x, v1.y) # 4, 6

这里我们定义了__iadd__方法,用于实现两个Vector对象使用+=时的相加操作。

__iadd__方法的参数是另一个要相加的对象,在方法内部我们实现了两个向量的分量相加,并返回self作为结果。这样就实现了+=的运算符重载。

此外,Python还提供了__add__特殊方法用于重载+符号,但是__iadd__和__add__有以下区别:

  • __add__返回一个新的对象,不改变原有对象。
  • __iadd__在原有对象的基础上进行操作,并返回对原对象的引用。

所以对可变对象进行+=操作时,通常需要实现__iadd__方法。

参考文献

https://www.runoob.com/python/python-object.html

Posted Updated Operating system42 minutes read (About 6276 words)

Context Switch

上下文切换

  • 根据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

machine system calls process context switches thread context switches thread context switches 2
snode6 428.6 2520.3 2606.3(1738.9) 277.8
snode6 427.7 2419.8 2249.0(2167.9) 401.1
snode6 436.0 2327.1 2358.8(1727.8) 329.3
hades 65.8 1806.4 1806.4 64.6
hades 65.5 1416.4 1311.6 282.7
hades 80.8 2153.1 1903.4 64.3
icarus 74.1 1562.3 1622.3 51.0*
icarus 74.1 1464.6 1274.1 232.6*
icarus 73.9 1671.8 1302.1 38.0*
vlab 703.4 5126.3 4897.7 826.1*
vlab x x x x
vlab 697.1 10651.4 4476.0 843.9*
docker ｜｜｜｜
docker ｜｜｜｜
docker ｜｜｜｜

说明:

  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
  1. 软件的不同
machine OS linux kernel compile glibc
snode6 Ubuntu 20.04.6 LTS 5.4.0-148-generic gcc 9.4.0 GLIBC 2.31
hades Ubuntu 22.04.2 LTS 5.15.0-76-generic gcc 11.3.0 GLIBC 2.35-0ubuntu3.1
icarus Ubuntu 22.04.2 LTS 5.15.0-75-generic gcc 11.3.0 GLIBC 2.35-0ubuntu3.1
vlab Ubuntu 22.04.2 LTS 5.15.81-1-pve gcc 11.3.0 GLIBC 2.35-0ubuntu3.1

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 文档

Follow

Categories

Subscribe for updates

follow.it

Links

Recents

Archives

Tags

5G1
64bits vs 32bits1
AI3
AMAT1
AMD3
ASPLOS1
ATI1
AVX2
Algorithm1
Alpha1
Analysis1
Apt1
Assembly4
BFS1
BHive1
BT3
BTL1
Baka Mitai1
Bash1
Big-Endian1
×