线段树（Segment Tree）是一种将数组区间存储为树的数据结构 ^1。

时间复杂度

查询连续子数组 或 查询范围内的最小元素：O(logn)

最简单形式的线段树

高阶版本的线段树

TODO

参考

OI wiki

在测试leetcode的 815.公交路线 一题时，发现一个现象，当我使用vector<vector<bool>>作为图的邻接矩阵的类型时，运行速度比使用vector<vector<int>>慢了近1倍。使用bool运行速度为600ms左右，使用int时运行速度为300ms左右。

以下是ChatGPT的回答：

在C++中，bool类型并不一定比int类型慢，但在某些情况下，它们的性能表现可能有所不同。以下是一些与性能差异相关的考虑：

1. 内存大小
   bool类型在标准中只需要表示 true（非0）和 false（0），通常占用1个字节（8位），而 int 通常占用4个字节（32位）。因此，bool类型可以节省内存，在某些情况下会带来缓存效率的提升，尤其是在处理大量布尔值时（例如布尔数组）。
2. 对齐和内存访问
   在某些架构上，处理单字节的bool类型时，可能会有额外的开销，因为处理器通常优化对齐访问。如果内存没有正确对齐，处理器可能需要额外的操作来处理非对齐的字节，导致性能下降。相比之下，int的对齐通常与系统的内存总线对齐更好（如32位或64位系统上），因此读取和写入可能更高效。
3. 指令集和操作
   现代处理器在处理布尔值时通常会将其扩展为完整的寄存器大小（例如32位或64位）。因此，虽然bool类型的存储可能更小，但在实际操作中，处理器可能将它提升为int或更大的类型来执行逻辑操作。处理布尔值可能涉及隐式类型转换，这在某些极端情况下可能带来开销。
4. 寄存器使用
   int 类型可以直接映射到处理器寄存器中进行操作，而 bool 类型的操作有时可能会涉及额外的逻辑运算（如掩码操作）以确保布尔值的正确性。
5. 编译器优化
   现代编译器在优化时会考虑到bool与int的差异，并尽量优化代码，因此在大多数应用场景下，你不会感受到显著的性能差异。但在一些特定的场合（如大规模数组、频繁内存访问等），bool类型的使用确实可能带来性能影响，尤其是在处理器需要对齐或执行额外的操作时。
   总结
   bool类型通常并不会比int慢，实际的性能差异取决于平台、内存对齐、编译器优化以及应用场景。在大多数情况下，差异是微不足道的，但在对性能非常敏感的程序中，这种差异可能会显现。

启用调试模式

1. 命令行启用调试：

1
2

#使用 -x 和 -v 选项运行 main.sh 脚本。
bash -xv main.sh

注意：调试输出是通过 stderr ，在试图重定向时要注意。

2. 在脚本中启用调试：

1

set -xv

参考链接

其他选项：

• set +e：忽略错误继续运行（bash）。
• set -e：遇错停止执行（bash）。

3. 环境变量 PS4

1

PS4='+ ${LINENO}: '

可以搭配使用 PS4 环境变量，以在调试输出中打印命令所在的文件行号。

PS4 是一个 Bash 环境变量，用于定义调试模式下的提示符格式。
当你启用调试模式（通过 set -x）时，Bash 会在每一行执行之前打印调试信息，而 PS4 决定了这些调试信息的格式。
$LINENO表示打印行号。

trap DEBUG

设置DEBUG陷阱，该陷阱在每一条“简单语句”执行完毕之后会被调用一次。

1
2
3
4
5
6
7
8
9
10
11

set -o functrace
track_var="my_var"
old_value=""
check_var_change() {
    new_value="${!track_var}"
    if [[ "$new_value" != "$old_value" ]]; then
        echo "$track_var changed to \"$new_value\" at $BASH_LINENO"
        old_value="$new_value"
    fi
}
trap check_var_change DEBUG

说明：监控my_var变量的变化，如果变化，则打印新值。

注意：实际测试中，我们发现trap监控变量变化似乎会延迟，而set -x打印的信息是可靠的。

特殊变量

参考：https://www.gnu.org/software/bash/manual/html_node/Bash-Variables.html

• BASH_LINENO: 这是一个数组变量，‌用于表示当前执行的脚本或函数中每一行的行号。‌它特别适用于调试，‌因为它可以追踪到函数调用栈中每一层的行号。‌通过访问BASH_LINENO数组的不同索引，‌可以获取到不同函数调用层级对应的行号信息‌。
• LINENO: 获取当前脚本行号‌，‌而不涉及函数调用栈的追踪‌。
• FUNCNAME: 函数名
• BASH_SOURCE

判断文件是否存在

相关函数

• access
• stat
• inotify_node
• opendir
• readdir

注意事项

文件系统并不会实时刷新缓存，尤其是在网络文件系统中。这会导致文件即使已经创建，access或stat函数依然返回”No such file”。
但是ls可以看到文件，这是因为ls和access函数的实现机制不同。

例如：

在NFS文件系统中，创建文件之后立即调用stat命令查看文件，stat会报告“文件不存在”。
删除文件之后立即调用stat命令查看文件，发现stat依然可以看到该文件。

我们可以改用readdir来读取目录，因为目录会被更快地更新缓存。

debug

在当前代码根目录下创建.vscode/launch.json 文件，写入如下内容：

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

{
  "configurations": [
    {
      "name": "(gdb) Launch",
      "type": "cppdbg",
      "request": "launch",
      "program": "${workspaceFolder}/a.out",
      "args": [],
      "stopAtEntry": true,
      "cwd": "${workspaceFolder}",
      "miDebuggerServerAddress": "<remote host>:<remote port>",
      "environment": [],
      "externalConsole": false,
      "MIMode": "gdb"
    },
    {
      "name": "(gdb) Attach",
      "type": "cppdbg",
      "request": "attach",
      // "program": "/path/to/executable",
      "program": "/proc/self/exe",
      "MIMode": "gdb",
      "setupCommands": [
        {
          "description": "Enable pretty-printing for gdb",
          "text": "-enable-pretty-printing",
          "ignoreFailures": true
        },
        {
          "description": "Set Disassembly Flavor to Intel",
          "text": "-gdb-set disassembly-flavor intel",
          "ignoreFailures": true
        }
      ]
    }
  ],
  "version": "2.0.0"
}

其中，”(gdb) Launch”可以用来连接 gdbserver。用 gdbserver 启动 executable：

1

gdbserver peer_host:local_port prog [args]

如果在点击”Run”按钮之前，在 VSCode 的 Debugger Terminal 写上命令（可以不按 Enter），那么在程序启动时
，该命令会被先执行。

clangd + vscode + Native Debug + gdbserver

Microsoft 的 C/C++ Extension Pack 跳转较慢，使用 clangd 会更快速。但是使用 clangd 后不能使用
cppdbg 类型来连接 gdbserver ，需要安装 Native Debug 插件，使用原始的 gdb 工具来连接 gdbserver 。

Attach to gdbserver

gdbserver 也可以使用 attach 的方式。

1

gdbserver --attach :port PID

.vscode/launch.json

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

{
  "configurations": [
    {
      "type": "gdb",
      "request": "attach",
      "name": "Attach to gdbserver",
      "executable": "/path/to/executable",
      "target": "[host]:<port>",
      "remote": true,
      "cwd": "${workspaceRoot}",
      "valuesFormatting": "parseText"
    }
  ]
}

Q & A

1. Q: Configured debug type 'cppdbg' is not supported.
A: Please check if the "c/c++" extension is installed. (ref)
2. Q: VS Code Remote-SSH: The vscode server failed to start SSH
A: https://stackoverflow.com/questions/67976875/vs-code-remote-ssh-the-vscode-server-failed-to-start-ssh
3. Q: Where does VS Code store the data for its Local History feature?
A: https://stackoverflow.com/questions/72610147/where-does-vs-code-store-the-data-for-its-local-history-feature
4. vscode无法跳转到定义
A: when "C_Cpp.intelliSenseEngine" is set to "Tag Parser", Goto definition is working fine.

https://github.com/microsoft/vscode-cpptools/issues/273

Links

• TI-RPC
• RPC language
• XDR Protocol
• PRC Compiler
• rpcgen
• rpcgen programming guide

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

$ which rpcgen
/bin/rpcgen
$ rpcgen
usage: rpcgen infile
        rpcgen [-abkCLNTM][-Dname[=value]] [-i size] [-I [-K seconds]] [-Y path] infile
        rpcgen [-c | -h | -l | -m | -t | -Sc | -Ss | -Sm] [-o outfile] [infile]
        rpcgen [-s nettype]* [-o outfile] [infile]
        rpcgen [-n netid]* [-o outfile] [infile]
options:
-a              generate all files, including samples
-b              backward compatibility mode (generates code for SunOS 4.1)
-c              generate XDR routines
-C              ANSI C mode
-Dname[=value]  define a symbol (same as #define)
-h              generate header file
-i size         size at which to start generating inline code
-I              generate code for inetd support in server (for SunOS 4.1)
-K seconds      server exits after K seconds of inactivity
-l              generate client side stubs
-L              server errors will be printed to syslog
-m              generate server side stubs
-M              generate MT-safe code
-n netid        generate server code that supports named netid
-N              supports multiple arguments and call-by-value
-o outfile      name of the output file
-s nettype      generate server code that supports named nettype
-Sc             generate sample client code that uses remote procedures
-Ss             generate sample server code that defines remote procedures
-Sm             generate makefile template 
-t              generate RPC dispatch table
-T              generate code to support RPC dispatch tables
-Y path         directory name to find C preprocessor (cpp)

For bug reporting instructions, please see:
<http://www.gnu.org/software/libc/bugs.html>.

Note:

% 可以用来转义某行，任何句首带有 % 的行将被视作字符串，直接放入到输出文件中。
注意：rpcgen 可能改变该行的位置，所以应该在输出文件中对这些行进行仔细检查。

rpcgen provides an additional preprocessing feature: any line that begins with a percent sign (%) is passed directly to the output file, with no action on the line’s content. Use caution because rpcgen does not always place the lines where you intend. Check the output source file and, if needed, edit it.

例如

1

#include "abc.h"

当执行 rpcgen infile 命令时，由于 “abc.h” 不存在，可能会报错。

但是如果在句首添加一个 % 符号，则可以绕过检查。

1

%#include "abc.h"

Link

Free English Class! Topic: Hair! 🧔🏽💇✂️ (Lesson Only)

Words/Phrases

eyelashes
makeup
hairstyle/hairdo
get my hair done
hair gel
buzz cut
helmet
When you have a lot of hair, the helmet makes your hair flat.
hair colouring

From ChatGPT:

In general, when a program enters a signal handler in a multi-threaded environment, the behavior regarding other threads depends on how the signal handler is set up and the specific signal that is being handled.

1. Default Behavior: By default, when a signal is delivered to a process, it interrupt the thread that is currently running and executes the signal handler in the context of that thread. Other threads in the process continue running unless they are also interrupted by signals.
2. Thread-Specific Signal Handling: Some signals, such as SIGINT (interrupt signal), SIGTERM (termination signal), or SIGABRT (abort signal), are typically delivered to the entire process, which means they can interrupt any thread. However, other signals, like SIGSEGV (segmentation fault) or SIGILL (illegal signal), are usually delivered to the specific thread that caused the signal.
3. Signal Masking: In a multi-threaded program, you can use signal masking (sigprocmask in POSIX systems) to block certain signals in specific threads. This can affect whether a signal handler interrupts a particular thread or not.
4. Asynchronous-Signal-Safe Functions: Signal handlers should only execute functions are considered “asynchronous-signal-safe” according to POSIX standards. These functions are designed to be safe to call from within a signal handler. Using non-safe functions in a signal handler can lead to undefined behavior.

安装

使用脚本一键监查系统是否安装了 TBB

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

#!/bin/bash
echo "==== 检查 Intel TBB (oneTBB) 安装情况 ===="

# 1. 包管理器检查
if command -v dpkg >/dev/null 2>&1; then
    echo "[dpkg] 检查:"
    dpkg -l | grep tbb || echo "  未找到 tbb 包 (Debian/Ubuntu)"
elif command -v rpm >/dev/null 2>&1; then
    echo "[rpm] 检查:"
    rpm -qa | grep tbb || echo "  未找到 tbb 包 (CentOS/RHEL)"
fi

# 2. pkg-config 检查
echo "[pkg-config] 检查:"
if command -v pkg-config >/dev/null 2>&1; then
    if pkg-config --exists tbb; then
        echo "  版本: $(pkg-config --modversion tbb)"
        echo "  CFLAGS: $(pkg-config --cflags tbb)"
        echo "  LIBS: $(pkg-config --libs tbb)"
    else
        echo "  未检测到 pkg-config 中的 tbb"
    fi
else
    echo "  系统未安装 pkg-config"
fi

# 3. 文件检查
echo "[文件] 检查:"
HEADER_PATH=$(find /usr/include /usr/local/include -type d -name tbb 2>/dev/null | head -n 1)
LIB_PATH=$(find /usr/lib /usr/local/lib /usr/lib64 -name "libtbb.*" 2>/dev/null | head -n 1)

if [ -n "$HEADER_PATH" ]; then
    echo "  头文件目录: $HEADER_PATH"
else
    echo "  未找到 tbb 头文件"
fi

if [ -n "$LIB_PATH" ]; then
    echo "  库文件: $LIB_PATH"
else
    echo "  未找到 tbb 库文件"
fi

# 4. 测试编译
echo "[编译测试] 尝试编译一个 TBB 示例..."
TMP_CODE=$(mktemp /tmp/test_tbb.XXXXXX.cpp)
cat > $TMP_CODE <<'EOF'
#include <tbb/tbb.h>
#include <iostream>
int main() {
    tbb::parallel_for(0, 5, [](int i){ std::cout << i << " "; });
    std::cout << std::endl;
    return 0;
}
EOF

g++ $TMP_CODE -o /tmp/test_tbb -ltbb -std=c++17 2>/tmp/tbb_err.log
if [ $? -eq 0 ]; then
    echo "  ✅ 编译成功，可以使用 TBB"
    /tmp/test_tbb
else
    echo "  ❌ 编译失败，错误信息如下："
    cat /tmp/tbb_err.log
fi

rm -f $TMP_CODE /tmp/test_tbb /tmp/tbb_err.log

从包管理器安装：

1
2

sudo apt update
sudo apt install libtbb-dev

用源码安装

如果需要最新版本，可以从 GitHub 获取 oneTBB

1
2
3
4
5
6

git clone https://github.com/oneapi-src/oneTBB.git
cd oneTBB
mkdir build && cd build
cmake ..
make -j$(nproc)
sudo make install

默认会安装到 /usr/local/include/ 和 /usr/local/lib/。

文档

官方文档：https://uxlfoundation.github.io/oneTBB/

1. TBB 调度原理

1.1. TBB 的任务调度模型

1.1.1. 线程池 + 任务队列

• TBB 不让你直接创建线程去执行任务，而是维护一个 固定大小的线程池（数量通常 = CPU 核心数）。
• 所有并行任务都被封装成 task，放入 任务队列。
• 每个工作线程从队列里取任务执行，执行完就取下一个任务。
• 这种模式叫 工作窃取（work-stealing）调度。

1.1.2. 工作窃取机制

• 每个线程有自己的双端队列（deque），优先从自己队列尾部取任务执行。
• 当线程自己的队列空了，会从别的线程队列头部 “窃取” 任务。

优点：

• 动态负载均衡：核心利用率高
• 减少锁竞争：线程多操作自己队列，窃取少量访问其他队列

1.1.2.1. 任务窃取的实现原理

1
2
3

tg.run(); // 非阻塞

tg.wait();  // 同步+非阻塞：调用线程会主动参与执行任务，CPU持续运行（非阻塞）

概念澄清：

• 同步：必须等所有任务完成。
• 非阻塞：线程没有闲等，而是参与执行任务。

当 tg.wait() 时，调用线程会帮忙执行任务，具体是如何实现的？

任务队列（Task Queue）

tg.run() 会把所有待执行的任务放入一个共享的队列（通常是无锁队列或工作窃取队列）。

每个工作线程（包括调用线程）都可以从队列里取任务来执行。

调用线程参与执行

当调用线程进入 tg.wait() 时，它不会只是挂起等待，而是：

• 检查任务队列是否还有未完成的任务。
• 如果有，就直接取出任务并执行。
• 执行完后再继续检查，直到所有任务完成。

完成条件

tg.wait() 内部会维护一个 任务计数器（例如原子变量），记录剩余任务数。

• 每个线程完成一个任务时，计数器减一。
• 当计数器归零时，说明所有任务都完成了，调用线程才真正返回。

避免死锁

调用线程必须能执行任务，否则如果它只是等待，而任务又依赖它执行，就会死锁。

所以 tg.wait() 的设计就是让调用线程也成为”工作线程”，保证任务能被及时调度。

1.2. 与直接使用 std::thread 的区别

1.3. 总结

TBB 高效的核心原因：

• 固定线程池：避免频繁创建销毁线程带来的开销
• 任务化设计：粒度灵活，任务比线程轻量
• 工作窃取：自动负载均衡，提高 CPU 利用率
• 减少锁竞争：每个线程大部分时间只操作自己的队列

所以，用 TBB 写 parallel_for 或 flow::graph 时，即使任务非常小，CPU 核心也能被充分利用，而直接 std::thread 很可能线程创建成本比任务本身还高，性能反而下降。

2. task_group

task_group 的本质

• tbb::task_group 是一种 轻量级任务管理器，用来组织一组并行任务。
• 它本身 不创建线程池，也不维护独立线程。
• 当你调用 task_group.run() 或 task_group.wait() 时：
• 任务会被 提交到当前上下文的线程池，通常是 全局线程池
• 由线程池中的工作线程去调度和执行

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

#include <tbb/tbb.h>
#include <unistd.h>

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

using namespace std;

std::mutex mtx;

void task_group_function() {
    tbb::task_group tg;
    int max_concurrency = tbb::this_task_arena::max_concurrency();
    {
        std::lock_guard<std::mutex> lock(mtx);
        cout << "Task group max concurrency: " << max_concurrency << endl;
    }
    for (int i = 0; i < 16; ++i) {
        tg.run([i] {
            {
                std::lock_guard<std::mutex> lock(mtx);
                std::cout << "Task group thread " << std::this_thread::get_id() << " is running." << std::endl;
            }
            sleep(1);
        });
    }
    tg.wait();
}

void task_arena_function() {
    tbb::task_arena arena(4);
    int max_concurrency = arena.max_concurrency();
    {
        std::lock_guard<std::mutex> lock(mtx);
        cout << "Task arena max concurrency: " << max_concurrency << endl;
    }
    arena.execute([max_concurrency] {
        tbb::parallel_for(0, 16, [](int i) {
            {
                std::lock_guard<std::mutex> lock(mtx);
                std::cout << "Task arena thread " << std::this_thread::get_id() << " is running." << std::endl;
            }
            sleep(2);
        });
    });
}

int main() {
    // 获取默认task_arena的最大并发线程数
    int arena_max_concurrency = tbb::this_task_arena::max_concurrency();
    std::cout << "Default task_arena max concurrency: " << arena_max_concurrency << std::endl;

    // 创建两个线程
    std::thread tg_thread(task_group_function);
    std::thread ta_thread(task_arena_function);

    // 等待两个线程完成
    tg_thread.join();
    ta_thread.join();

    return 0;
}

测试：

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

$ mkdir build && cd build && cmake .. && make
$ ./tbb_thread_pool > result.txt
$ cat result.txt | grep running | sort | uniq
Task arena thread 140667163379264 is running.
Task arena thread 140667167639104 is running.
Task arena thread 140667184678464 is running.
Task arena thread 140667201848896 is running.
Task group thread 140667167639104 is running.
Task group thread 140667171898944 is running.
Task group thread 140667176158784 is running.
Task group thread 140667180418624 is running.
Task group thread 140667188938304 is running.
Task group thread 140667210303040 is running.

从这两行日志可以看出，arena 和 group 重用了同一个线程 ID ，说明它们同属于同一个全局线程池。

1
2

Task arena thread 140667167639104 is running.
Task group thread 140667167639104 is running.

进一步，我们发现全局线程池中的线程总数是自适应的，比如本例就是 10 个，既不是 task_group 的 8 个，
也不是 task_arena 的 4 个：

TODO

1
2

$ cat result.txt | grep running | sort | uniq | wc -l
10

3. task_arena

TBB 是基于任务，不是基于线程。但是如果你想修改 TBB 的线程数，有两种方法：

• 方法一：使用环境变量 TBB_NUM_THREADS 进行全局设置：

1

export TBB_NUM_THREADS=4

TODO: It doesn’t seem to work!

• 方法二：使用 tbb::task_arena or tbb::task_scheduler_init (Deprecated) 进行线程隔离。

TBB will use this setting locally within the scope of the tbb::task_arena.

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

#include <tbb/pipeline.h>
// Deprecated:
// #include <tbb/task_scheduler_init.h>
#include <tbb/task_arena.h>

// Define your pipeline body
class MyPipeline {
public:
    void operator() (tbb::flow_control& fc) const {
        // Your pipeline logic here
        // ...
        // Inform the pipeline that there is no more data
        fc.stop();
    }
};

int main() {
    // Deprecated: tbb::task_scheduler_init init(1);
    tbb::task_arena arena(4); // 4 threads
    // Do some tasks:
    tbb::parallel_pipeline(/* max_number_of_live_tokens */ 4, MyPipeline); // FIXME: 似乎需要放入 arena 的 execute 函数中

    return 0;
}

task_arena 默认 不会去窃取全局线程池的线程

1. task_arena 的线程隔离

tbb::task_arena 是 局部线程池的抽象，可以指定线程数量和优先级。

在 arena.execute(…) 里执行的任务：

优先使用 task_arena 自己的线程（如果 arena 里有空闲线程）

不会去窃取全局线程池的线程

也就是说，task_arena 内的任务和全局线程池是相对隔离的。

2. 嵌套并行和空闲线程利用

如果 task_arena 内的线程空闲不足，默认不会去全局线程池窃取线程。

但是 TBB 内部可能会将一些未使用的线程调度给 arena，但这属于内部优化，不等同于直接窃取整个全局线程池。

总体原则：arena 控制自己的线程数，不影响全局线程池。

3. 全局线程池 vs task_arena 总结

4. 小结

• 默认情况下，全局线程池是唯一的，TBB 所有普通并行调用都会复用它。
• task_arena 提供局部线程池，在其作用域内执行的任务主要使用 arena 的线程，不去抢全局线程池。
• 用 task_arena 可以做局部限制（比如 GUI 线程或限制 CPU 核心占用），对全局线程池影响很小。

4. parallel_for

API: parallel_for

1. 用 my_parallel_for 模拟 parallel_for 的实现：

2. 发出任务的线程也会成为工作线程之一，并参与任务的执行，测试代码如下：

测试结果：

1
2
3
4
5
6
7

$ ./test_parallel_for
Main thread ID: 140220582070080
Processing data: 2 on thread 140220582070080
Processing data: 6 on thread 140220557755968
Processing data: 4 on thread 140220574795328
Processing data: 8 on thread 140220566275648
Processing data: 10 on thread 140220562015808

可见，data 2 是由主线程处理的。也就是说，parallel_for 虽然被称为 a blocking parallel construt，但线程等待所有任务完成期间是非阻塞的，它还可以充当工作线程执行任务池中的任务。

代码模拟 parallel_for 的 wait ：

5. 任务调度器（Task Scheduler）

The Task Scheduler

5.1. 基于任务编程（Task-Based Programming）

当追求性能时，推荐以逻辑任务（logical tasks）而不是线程（threads）来编程，有以下原因：

• 将并行性与可用资源匹配
• 更快的任务启动和关闭
• 更有效的评估顺序
• 改进负载均衡
• 更高层的思考

TODO

5.2. 任务调度器（Task Scheduler）如何工作

How Task Scheduler Works

5.2.1. 深度优先（depth-first）

每个线程都有自己的双端队列，头部称为 top （也称顶部），尾部称为 bottom （也称底部）。
队列的底部是队列的最深处（最末处），底部任务是最新的，顶部任务是最旧的。

深度优先有以下好处：

• 热点缓存命中：最新的任务的缓存是最热的，所以优先执行新任务。
• 最小化空间：广度优先会同时创建指数级数量的共存节点，而深度优先虽然也会创建相同数量的节点，但是只有线性数目的节点会同时共存，因为它创建了其他就绪任务的栈。

生产：当线程产生一个任务时，将其放置到线程自身所有的 deque 的尾部。

消费：当线程执行任务时，根据以下规则顺序选取一个任务：

• 规则 1：获取上一个任务返回的任务，如果有；
• 规则 2：从线程自己所有的 deque 尾部选取一个任务（即深度优先），如果有；
• 规则 3：随机选择一个其他线程的 deque ，从其头部窃取一个任务（即广度优先）。如果被选 deque 为空，则重复本条规则直至成功。

规则 1 被称为 “任务调度绕行（Task Scheduler Bypass）”。

规则 2 是深度优先，这使得当前线程得以不断执行最新的任务直至其完成所有工作。

规则 3 是临时的广度优先，它将潜在的并行转化为实际的并行。

5.2.2. 任务调度绕行（Task Scheduler Bypass）技术

一个任务从产生到被执行涉及以下步骤：

• 将新任务加入线程的 deque 。
• 执行当前任务直至完成。
• 从线程 deque 获取一个任务执行，除非该任务被其他线程窃取走了。

其中，步骤 1 和 步骤 3 会引入不必要的 deque 操作，甚至更糟的是，允许窃取会损害局部性而不会增加显著的并行性。
任务调度器绕行技术可以直接指向下一个要被执行的任务，而不是生产该任务，从而避免了上述问题。
因为根据 “规则 1”，上一个任务产生的新任务会称为第一个备选任务。
此外，该技术几乎保证了该新任务被当前线程执行，而不是其他线程。

注意：当前唯一能使用该优化技术的是使用 tbb::task_group 。

5.3. 指导任务调度器的执行（Guiding Task Scheduler Execution）

Guiding Task Scheduler Execution

默认情况下，任务计划程序会尝试使用所有可用的计算资源。在某些情况下，您可能希望将任务计划程序配置为仅使用其中的一些资源。

注意：指导任务调度程序的执行可能会导致可组合性问题。

TBB 提供 task_arena 接口，通过以下方式指导任务在 arena （竞技场）内被执行:

• 设置首选计算单元；
• 限制部分计算单元。

5.4. 工作隔离（Work Isolation）

Work Isolation

如果当前线程被 parallel_for “阻塞”（不是真正的阻塞，只能称为 a blocking parallel construct），那么该线程被允许拿取第一个循环的任务来执行。这会导致即使是同一个线程内，也可出现乱序执行的情况。在大多数情况下，这没有什么危害。

但是少数情况可能出现错误，例如一个 thread-local 变量可能会在嵌套并行构造之外意外被更改：

在其它场景下，这种行为可能会导致死锁或其他问题。在这些情况下，需要更有力地保证线程内的执行次序。为此，TBB 提供了一些隔离并行构造的执行的方法，以使其任务不会干扰其他同时运行的任务。

其中一种方法是在单独的 task_arena 中执行内层循环：

然而，使用单独的 arena 进行工作隔离并不总是方便的，并且可能会产生明显的开销。为了解决这些缺点，TBB 提供 this_task_arena::isolate 函数，通过限制调用线程仅处理在函数对象范围内（也称为隔离区域）安排的任务，来隔离地运行一个用户提供的函数对象。

当一个线程进入一个任务等待调用或（等待）在一个隔离区域内的阻塞并行结构时，该线程只能执行在该隔离区域内生成的任务及其由其他线程生成的子任务（换句话说，即使子任务是由其他线程生成的，只要属于当前隔离区域，当前线程也可以执行这些任务）。线程被禁止执行任何外层任务或属于其他隔离区域的任务。

下面的示例展示了 this_task_arena::isolate 的使用，以保证在嵌套的并行结构调用时， thread-local 变量不会被意外修改：

** 补充：** 让我们通过一个简单的例子来说明隔离区域内其他线程如何生成子任务，并且这些子任务可以由当前线程执行。

假设我们有一个隔离区域，其中有两个线程：线程 A 和线程 B。我们在这个隔离区域内生成了一些任务，并且这些任务可能会生成子任务。

在这个例子中：

taskA 和 taskB 是在隔离区域内生成的任务。
taskA 生成了两个子任务 Subtask A1 和 Subtask A2。
taskB 生成了两个子任务 Subtask B1 和 Subtask B2。
假设线程 A 执行了 taskA，线程 B 执行了 taskB。在隔离区域内，线程 A 和线程 B 可以执行彼此生成的子任务。例如，线程 A 可以执行 Subtask B1 或 Subtask B2，而线程 B 可以执行 Subtask A1 或 Subtask A2，只要这些子任务属于同一个隔离区域。

6. TBB 的无锁设计

严格来说，TBB 并不是完全无锁，但它尽量采用 无锁（lock-free）设计 来提高性能。下面详细说明：

a. 无锁设计的部分

• 工作窃取双端队列（deque）

  • 线程自己的尾部操作（push/pop）通常是 无锁
  • 窃取线程从头部 steal 任务使用 原子 CAS（Compare-And-Swap），也是无锁操作

• 并行算法（parallel_for, parallel_reduce）

  • 内部任务调度和分割通常用无锁队列 + 原子操作

• 轻量级任务对象（task）引用计数

  • 使用原子操作维护任务生命周期，不依赖互斥锁

总结：TBB 在任务调度和工作窃取上，尽量用无锁和原子操作，保证高性能并发执行。

b. 仍然存在锁的场景

• 队列扩容（grow）

  • 当线程队列满，需要扩容底层数组时会使用轻量锁保护

• 某些并行容器

  • concurrent_hash_map, concurrent_vector 等在处理极端并发情况时会使用锁（有时是读写锁）

• 全局管理或 arena 初始化

  • 初始化线程池、任务调度器时可能使用锁，通常只在启动阶段发生

6.1. 总结

7. TBB 的线程生命期

是的，即使你只调用一次 TBB 并行函数，线程池创建后在整个程序运行期间也不会自动销毁或减少线程数。具体说明如下：

1. 全局线程池生命周期

TBB 默认全局线程池是在 第一次使用 TBB 并行接口时创建的。
线程数固定（通常等于 CPU 核心数），整个程序运行期间一直存在。
不会因为你长时间没有提交任务而销毁线程，也不会自动减少线程数。

2. 线程状态

长时间不使用 TBB 时，线程 处于空闲等待状态，不会占用 CPU。
内存占用仍然存在，因为线程堆栈和线程管理结构仍在。
一旦再次调用 TBB 并行函数，线程立即复用，无需重新创建。

3. 可控策略

如果希望线程在长时间不使用时释放资源，可以：
手动控制线程池生命周期（较复杂，需深入 TBB 内部 API，不推荐）
程序设计上在长时间空闲时退出进程，释放所有线程和内存
一般服务器程序会让线程池持续存在，利用 TBB 的工作窃取和线程复用优势，提高后续任务性能。

✅ 总结

TBB 线程池线程数固定，不会因长时间不使用而减少。
线程空闲时不占用 CPU，但占用内存和线程管理资源。
这种设计是为了 提高任务再次执行的响应速度，适合服务器或长期运行的高性能程序。

8. TBB 是 CPU 密集型的

如果你的程序有大量 I/O 操作，使用 TBB 的一些特点和注意事项需要特别留意，因为 TBB 是为 CPU 密集型任务 和 任务并行化 设计的。具体分析如下：

1. TBB 对 I/O 的特点

• 线程池固定，线程数通常 = CPU 核心数
• 每个线程会被用来执行任务，如果任务中 发生阻塞 I/O（如文件读写、网络请求）：
• 阻塞线程会占用线程池的一个线程
• 其他任务可能因为线程不足而等待

结论：TBB 默认不适合大量阻塞 I/O 的场景

2. 常见问题

3. 解决方法

a. 分离 I/O 线程

不要在 TBB 线程池中直接做阻塞 I/O
可以开独立线程或线程池专门处理 I/O
TBB 线程只处理 CPU 密集型任务

b. 使用异步 I/O

对网络 / 文件 I/O 使用非阻塞或异步 API（如 asio、io_uring）
任务提交给 TBB 时 立即返回，I/O 完成通过回调或 future 处理

c. task_arena + 限制线程

如果必须在 TBB 线程里做少量阻塞 I/O，可以创建一个 局部 task_arena，限制线程数，避免阻塞全局线程池

d. 混合模型

CPU 密集任务用 TBB
阻塞 I/O 用专门线程池 / 异步框架
最后用 future/promise 或 task_group 协调结果

4. 总结

TBB 是 CPU 密集型并行框架，不适合大量阻塞 I/O
阻塞 I/O 会占用线程池线程，降低并行度

建议：

分离 I/O 线程或线程池
使用异步 I/O
TBB 只处理计算任务

9. 推荐阅读

1. Intel Building Blocks 编程指南. James Reinders.
2. Patterns for Parallel Pragramming. Timothy Mattson 等.
3. 设计模式：Design Patterns of Reusable Object-Oriented Software (Addison Wesley). Gamma, Helm, Johnson 和 Vlissides.

gcc

gcc是一个编译套件，包含c、c++、Fortran语言的编译器。

glibc

glibc是一个library，为C程序提供基础公共功能，包括系统调用、数学函数和其他核心组件。
Linux平台和vscode似乎都依赖glibc，如果擅自将LD_LIBRARY_PATH更改为其他版本的glibc路径，则bash会直接crash。

glibc包含以下bin和lib：

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

$ cd glibc-v2.34/Linux/RHEL7.0-2017-x86_64/bin && ls
catchsegv  getconf  iconv  locale     makedb  pcprofiledump  sotruss  tzselect  zdump
gencat     getent   ldd    localedef  mtrace  pldd           sprof    xtrace

# 进入其他版本的glibc/lib目录执行ls命令会报错，大概原因可能是因为当前路径的glibc的lib和系统的lib冲突。
$ cd ../lib && ls
ls: relocation error: ./libc.so.6: symbol __tunable_get_val, version GLIBC_PRIVATE not defined in file ld-linux-x86-64.so.2 with link time reference

$ cd .. && ls lib
Mcrt1.o               libanl.so.1             libm.so             libnss_hesiod.so.2
Scrt1.o               libc.a                  libm.so.6           libpcprofile.so
audit                 libc.so                 libmcheck.a         libpthread.a
crt1.o                libc.so.6               libmemusage.so      libpthread.so.0
crti.o                libc_malloc_debug.so    libmvec.a           libresolv.a
crtn.o                libc_malloc_debug.so.0  libmvec.so          libresolv.so
gconv                 libc_nonshared.a        libmvec.so.1        libresolv.so.2
gcrt1.o               libcrypt.a              libnsl.so.1         librt.a
ld-linux-x86-64.so.2  libcrypt.so             libnss_compat.so    librt.so.1
libBrokenLocale.a     libcrypt.so.1           libnss_compat.so.2  libthread_db.so
libBrokenLocale.so    libdl.a                 libnss_db.so        libthread_db.so.1
libBrokenLocale.so.1  libdl.so.2              libnss_db.so.2      libutil.a
libSegFault.so        libg.a                  libnss_dns.so.2     libutil.so.1
libanl.a              libm-2.34.a             libnss_files.so.2
libanl.so             libm.a                  libnss_hesiod.so

查看glibc的版本：

1
2

# 从上可知，ldd是glibc的核心组件之一
$ ldd --version

寻找libc.so的路径：

1
2
3
4
5
6
7
8

$ locate libc.so
/usr/lib/x86_64-linux-gnu/libc.so
/usr/lib/x86_64-linux-gnu/libc.so.6
$ locate libstdc++.so
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.so
/usr/lib/x86_64-linux-gnu/libstdc++.so.6
/usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.30
/usr/share/gdb/auto-load/usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.30-gdb.py

安装glibc：

Ubuntu平台

1

sudo apt-get install lib6

RedHat平台

1

sudo yum install glibc

检查GNC C++ Library (libstdc++)的版本：

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

$ strings /usr/lib/libstdc++.so.* | grep LIBCXX
[sjcvl-zhigaoz ] /lan/cva_rel/vxe_main/24.02.650.d000/tools.lnx86/lib/64bit % strings /usr/lib/libstdc++.so.* | grep LIBCXX
GLIBCXX_3.4
GLIBCXX_3.4.1
GLIBCXX_3.4.2
...
GLIBCXX_3.4.19
GLIBCXX_DEBUG_MESSAGE_LENGTH

$ strings /usr/lib/libc.so.* | grep GLIBC
GLIBC_2.0
GLIBC_2.1
GLIBC_2.1.1
...
GLIBC_2.17
GLIBC_PRIVATE

如果你有一个使用了libstdc++的特定的binary或application，可以用下面的命令来检查其版本：

1

$ ldd <your_binary_or_application> | grep libstdc++

使用vscode的“Remote SSH”工具试图连接到Linux时，可能会报错如下：

Warning: Missing GLIBCXX >= 3.4.25! from /usr/lib64/libstdc++.so.6.0.19
Warning: Missing GLIBC >= 2.28! from /usr/lib64/libc-2.17.so
Error: Missing required dependencies. Please refer to our FAQ https://aka.ms/vscode-remote/faq/old-linux for additional information.

这是因为Linux系统上的glibc版本中不包含GLIBCXX_3.4.25及以上的版本。此时需要降级vscode（建议做法）或升级glibc（似乎很难）。

让某些程序默认使用你本地安装的 glibc

你可以让某些程序默认使用你本地安装的 glibc（比如 ~/local/glibc-2.42），但不能全局替换系统默认 glibc，否则会导致系统崩溃。下面是几种安全又实用的方法，让你的程序“默认”使用本地 glibc：

✅ 方法一：使用 LD_LIBRARY_PATH 环境变量（推荐）
这是最简单的方式，让你运行的程序优先使用你指定的 glibc：

1

export LD_LIBRARY_PATH=$HOME/local/glibc-2.42/lib:$LD_LIBRARY_PATH

你可以把这行加到 ~/.bashrc 或 ~/.profile 中，这样每次登录都会自动生效。

📌 注意：这只影响你当前用户的 shell 环境，不会影响系统服务或其他用户。

✅ 方法二：使用 ld.so.preload（⚠️危险，不推荐）
你可以将本地 glibc 的路径写入 /etc/ld.so.preload，让系统优先加载它。但这会影响所有程序，包括 ls、bash、sudo 等，一旦路径错误，系统可能无法启动。

1

echo "$HOME/local/glibc-2.42/lib/libc.so.6" | sudo tee /etc/ld.so.preload

⚠️ 强烈不建议使用此方法，除非你在容器或 chroot 环境中测试。

✅ 方法三：使用 patchelf 修改程序的动态链接器
你可以用 patchelf 工具修改 ELF 程序的运行时 glibc 路径：

1
2
3

patchelf --set-interpreter $HOME/local/glibc-2.42/lib/ld-2.42.so \
         --set-rpath $HOME/local/glibc-2.42/lib \
         ./your_program

这样修改后的程序会自动使用你指定的 glibc，无需额外设置。

✅ 方法四：编译时指定 glibc 路径（适用于 CMake/GCC）
如果你自己编译程序，可以在编译时指定 glibc 的头文件和库路径：

1
2
3
4

gcc -I$HOME/local/glibc-2.42/include \
    -L$HOME/local/glibc-2.42/lib \
    -Wl,--rpath=$HOME/local/glibc-2.42/lib \
    your_code.c -o your_program

或者在 CMake 中设置：

1

set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -Wl,-rpath=$HOME/local/glibc-2.42/lib")

🧠 总结：推荐做法

🔍 编译器如何找到 glibc

1. 默认系统路径
   GCC 默认会在系统的标准库路径中查找 glibc，例如：

/lib
/lib64
/usr/lib
/usr/lib64
/usr/include（头文件）

这些路径通常由系统预设，glibc 安装时会自动放置在这些位置。

2. 头文件与动态库
   编译阶段：GCC 会使用 /usr/include 下的 glibc 头文件（如 stdio.h, stdlib.h）来进行语法检查和类型推导。

链接阶段：GCC 会调用链接器（ld），查找 libc.so.6 或 libc.a 来完成符号解析。

3. 环境变量控制
   你可以通过环境变量来影响 GCC 查找 glibc 的位置：

C_INCLUDE_PATH：指定头文件搜索路径

LIBRARY_PATH：指定库文件搜索路径

LD_LIBRARY_PATH：运行时动态库搜索路径

例如：

bash
export C_INCLUDE_PATH=/opt/glibc/include
export LIBRARY_PATH=/opt/glibc/lib
4. 链接器参数
你也可以通过 GCC 的 -Wl 参数直接告诉链接器使用哪个 glibc：

bash
gcc hello.c -o hello
-Wl,–dynamic-linker=/opt/glibc/lib/ld-2.34.so
-L/opt/glibc/lib
这会指定使用 /opt/glibc/lib/libc.so.6 和对应的动态链接器。

5. 使用 patchelf 工具修改依赖
   如果你已经编译好了程序，但想修改它使用的 glibc，可以用 patchelf：

bash
patchelf –set-interpreter /opt/glibc/lib/ld-2.34.so hello
patchelf –replace-needed libc.so.6 /opt/glibc/lib/libc.so.6 hello
这在部署多版本 glibc 时非常有用。

🧪 如何验证 glibc 的使用情况
查看程序依赖的 glibc：

bash
ldd ./hello
查看系统 glibc 版本：

bash
ldd