跳转至

2023

  • 分类于 Architecture
  • 需要 3 分钟阅读时间

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

Library

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。详细依赖见

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++库的位置：
g++ -print-file-name=libstdc++.so

或者

gcc -print-file-name=libstdc++.so
  1. 使用ldconfig命令查找：ldconfig是Linux系统中用于配置动态链接器的命令。您可以运行以下命令来查找libstdc++库的路径：
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++标志。例如：

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

希望这些方法能够帮助您找到libstdc++库并解决您的问题。如有更多问题，请随时向我询问。

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

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

无

  • 分类于 Algorithms
  • 需要 3 分钟阅读时间

Dynamic Programming

动态规划简介

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

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

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

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

性质：

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

基本思路

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

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

难点，重点

如何找到转移关系：

  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-2k+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 背包问题 
      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代码 

function climbStairs(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  return climbStairs(n - 1) + climbStairs(n - 2);
}
添加与DFS参数相关的记忆化数组，将这个 dfs 改成「无需外部变量」的 dfs。 
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

  • 分类于 Programming
  • 需要 2 分钟阅读时间

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)

  2. 定义在类内部,但不在任何方法之内

  3. 被该类的所有实例对象所共享
  4. 可以通过类名或实例对象访问

  5. 用于定义与这个类相关的特征或属性

  6. 实例变量(Instance Variable)

  7. 定义在类内部的方法之内

  8. 每个实例对象拥有属于自己的变量副本
  9. 只能通过实例对象访问
  10. 用于定义实例对象的个性化特征或状态

例如:

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面向对象的关键。

创建

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 关键字，换成其他词语也行。

创建实例对象与访问

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

继承

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

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

调用基类

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

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类继承的关键点。

运算符重载

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

+=

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

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

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__方法。

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

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

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

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
  2. The processor registers need to be saved and restored,
  3. the OS kernel code (scheduler) must execute,
  4. the TLB entries need to be reloaded,
  5. and processor pipeline must be flushed
  6. cache interference cost or indirect cost of context switch.
  7. 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

可用代码

# 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个核组，应该就能测量上下文切换。
# 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. 这个实验测量了 在两个核间的线程切换吗？没绑定应该是多核
  4. 为什么taskset绑定在同一个核反而变慢了呢。snode6
    1. timetctxsw2 340 -> 550
    2. timetctxsw 括号内数据 1712 -> 2225
  5. 同一个核有资源竞争吗？

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

# 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新产品的硬件确实有特殊设计
 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 核心的状态，常见的取值有：
  3. 0：表示该 CPU 核心不属于 node0。
  4. 1：表示该 CPU 核心属于 node0。 这种映射信息可以帮助系统管理员和开发人员了解系统的 NUMA 结构，以及每个 NUMA 节点上的 CPU 核心分布情况。通过查看这些信息，可以更好地优化任务和进程的分配，以提高系统的性能和效率。
# 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内核的角度
  2. 理解相关概念的使用 ASID PCID
  3. 用户态，内核态的概念，切换的细节以及开销
    1. 内核态的代码是共享的吗？内核态的操作有什么？
  4. 各部分的时间占比
  5. 学会测量时间

参考文献

上面回答部分来自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 文档

  • 分类于 Programming
  • 需要 2 分钟阅读时间

Language

面向过程 VS 面向对象

面向过程

面向过程是一种以事件为中心的编程思想，编程的时候把解决问题的步骤分析出来，然后用函数把这些步骤实现，在一步一步的具体步骤中再按顺序调用函数。

面向对象

在日常生活或编程中，简单的问题可以用面向过程的思路来解决，直接有效，但是当问题的规模变得更大时，用面向过程的思想是远远不够的。所以慢慢就出现了面向对象的编程思想。世界上有很多人和事物，每一个都可以看做一个对象，而每个对象都有自己的属性和行为，对象与对象之间通过方法来交互。面向对象是一种以“对象”为中心的编程思想，把要解决的问题分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描叙某个对象在整个解决问题的步骤中的属性和行为。

优缺点

面向过程

优点：

  1. 流程化使得编程任务明确，在开发之前基本考虑了实现方式和最终结果，具体步骤清楚，便于节点分析。
  2. 效率高，面向过程强调代码的短小精悍，善于结合数据结构来开发高效率的程序。

缺点：

  1. 需要深入的思考，耗费精力，代码重用性低，扩展能力差，后期维护难度比较大。
面向对象

优点:

  1. 结构清晰，程序是模块化和结构化，更加符合人类的思维方式；
  2. 易扩展，代码重用率高，可继承，可覆盖，可以设计出低耦合的系统；
  3. 易维护，系统低耦合的特点有利于减少程序的后期维护工作量。

缺点：

  1. 开销大，当要修改对象内部时，对象的属性不允许外部直接存取，所以要增加许多没有其他意义、只负责读或写的行为。这会为编程工作增加负担，增加运行开销，并且使程序显得臃肿。
  2. 性能低，由于面向更高的逻辑抽象层，使得面向对象在实现的时候，不得不做出性能上面的牺牲，计算时间和空间存储大小都开销很大。

静态语言 vs 动态语言

  1. Dynamic Programming Language (动态语言或动态编程语言)
  2. 动态语言，准确地说，是指程序在运行时可以改变其结构：新的函数可以被引进，已有的函数可以被删除等在结构上的变化。
  3. 比如众所周知的ECMAScript(JavaScript)便是一个动态语言。
  4. 除此之外如Ruby、Python等也都属于动态语言，而C、C++等语言则不属于动态语言。
  5. Dynamically Typed Language (动态类型语言)
  6. 动态类型语言：是指在运行期间才去做数据类型检查的语言。
  7. 在用动态语言编程时，不用给变量指定数据类型，该语言会在你第一次赋值给变量时，在内部将数据类型记录下来。
  8. Statically Typed Language (静态类型语言)
  9. 静态类型语言：与动态类型语言刚好相反，它的数据类型检查发生在在编译阶段，也就是说在写程序时要声明变量的数据类型。
  10. C/C++、C#、JAVA都是静态类型语言的典型代表。

两者的优缺点

静态类型语言的

  1. 主要优点在于其结构非常规范，便于调试，方便类型安全；
  2. 缺点是为此需要写更多的类型相关代码，导致不便于阅读、不清晰明了。

动态类型语言的

  1. 优点在于方便阅读，不需要写非常多的类型相关的代码；
  2. 缺点自然就是不方便调试，命名不规范时会造成读不懂，不利于理解等。

runtime

runtime 描述了程序运行时候执行的软件/指令， 在每种语言有着不同的实现。

可大可小，在 C 中，runtime 是库代码， 等同于 C runtime library，一系列 C 程序运行所需的函数。

在 Java 中，runtime 还提供了 Java 程序运行所需的虚拟机等。

总而言之，runtime 是一个通用抽象的术语，指的是计算机程序运行的时候所需要的一切代码库，框架，平台等。

Go中的 runtime

在 Go 中， 有一个 runtime 库，其实现了垃圾回收，并发控制， 栈管理以及其他一些 Go 语言的关键特性。 runtime 库是每个 Go 程序的一部分，也就是说编译 Go 代码为机器代码时也会将其也编译进来。所以 Go 官方将其定位偏向类似于 C 语言中的库。

Go 中的 runtime 不像 Java runtime （JRE， java runtime envirement ) 一样，jre 还会提供虚拟机， Java 程序要在 JRE 下 才能运行。

垃圾回收机制(garbage collection,GC)的设计

C/C++语言为什么没有对指针对象的垃圾回收机制

作为支持指针的编程语言，C++将动态管理存储器资源的便利性交给了程序员。在使用指针形式的对象时(请注意，由于引用在初始化后不能更改引用目标 的语言机制的限制，多态性应用大多数情况下依赖于指针进行)，程序员必须自己完成存储器的分配、使用和释放，语言本身在此过程中不能提供任何帮助。

某些语言提供了垃圾回收机制，也就是说程序员仅负责分配存储器和使用，而由语言本身负责释放不再使用的存储器，这样程序员就从讨厌的存储器管理的工作中脱身了。

C++的设计者Bjarne Stroustrup对此做出过解释：

“我有意这样设计C++，使它不依赖于自动垃圾回收(通常就直接说垃圾回收)。这是基于自己对垃圾回收系统的经验，我很害怕那种严重的空间和时间开销，也害怕由于实现和移植垃圾回收系统而带来的复杂性。还有，垃圾回收将使C++不适合做许多底层的工作，而这却正是它的一个设计目标。但我喜欢垃圾回收 的思想，它是一种机制，能够简化设计、排除掉许多产生错误的根源。 需要垃圾回收的基本理由是很容易理解的：用户的使用方便以及比用户提供的存储管理模式更可靠。而反对垃圾回收的理由也有很多，但都不是最根本的，而是关于实现和效率方面的。 已经有充分多的论据可以反驳：每个应用在有了垃圾回收之后会做的更好些。类似的，也有充分的论据可以反对：没有应用可能因为有了垃圾回收而做得更好。 并不是每个程序都需要永远无休止的运行下去；并不是所有的代码都是基础性的库代码；对于许多应用而言，出现一点存储流失是可以接受的；许多应用可以管理自己的存储，而不需要垃圾回收或者其他与之相关的技术，如引用计数等。 我的结论是，从原则上和可行性上说，垃圾回收都是需要的。但是对今天的用户以及普遍的使用和硬件而言，我们还无法承受将C++的语义和它的基本库定义在垃圾回收系统之上的负担。”

强类型语言和弱类型语言

1.强类型语言：使之强制数据类型定义的语言。没有强制类型转化前，不允许两种不同类型的变量相互操作。强类型定义语言是类型安全的语言，如Rust, Java、C# 和 Python，比如Java中“int i = 0.0;”是无法通过编译的；

2.弱类型语言：数据类型可以被忽略的语言。与强类型语言相反, 一个变量可以赋不同数据类型的值，允许将一块内存看做多种类型，比如直接将整型变量与字符变量相加。C/C++、PHP都是弱类型语言，比如C++中“int i = 0.0;”是可以编译运行的；

注意，强类型语言在速度上略逊色于弱类型语言，使用弱类型语言可节省很多代码量，有更高的开发效率。而对于构建大型项目，使用强类型语言可能会比使用弱类型更加规范可靠。

ispc

a data-parallel languagedesigned specifically to target Intel’s vector extensions

Intel® Implicit SPMD Program Compiler

An open-source compiler for high-performance SIMD programming on the CPU and GPU

ispc is a compiler for a variant of the C programming language, with extensions for "single program, multiple data" (SPMD) programming.

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

https://blog.csdn.net/yuanmengong886/article/details/52572533

https://segmentfault.com/a/1190000022715733

  • 分类于 Math
  • 需要 2 分钟阅读时间

Mathematical Logic & Algebraic structure

数学的黑洞

启发来源1

理发师悖论，与罗素悖论

与排除自指的数学体系类型论

希尔伯特纲领

  • 形式语言 公理，来建立数学。
    • 公理：约定俗成的命题，两点成一线 。算术的皮亚诺公理。
    • 形式语言：所有的句子变成符号: 存在任意量词 + 与或非 + 命题
  • 完备性Completeness ，一致性Consistency ，可判断性 Decidability
形式语言: f(x)在p处的极限为L
\[(\forall \varepsilon \gt 0)(\exist \delta \gt 0)(\forall x \in \R)(0 \gt |x-p|\gt\delta\Longrightarrow|f(x)-L|\lt\varepsilon)\]

哥德尔不完备定理

(即使排除了自指，还是不完备的)

数理逻辑 Mathematical logic

数理逻辑的奥秘在于，它试图将人类主观的推理思维过程客观化，并建立起主观推理与客观证明之间的联系。通过对形式语言的公理化来达到自然语言的公理化目标。

形式逻辑系统 与 一阶逻辑

  • 形式逻辑系统 （Formal logical systems）是数理逻辑表示的方法。
  • 一阶逻辑（英语：First-order logic），又称谓词逻辑（predicate logic）、量化逻辑（quantificational logic）、一阶谓词演算（first-order predicate calculus）2
  • 一阶逻辑在非逻辑对象上使用量化的变量，并且允许使用包含变量的句子，这样就可以有“存在x，使得x是苏格拉底并且x是人”形式的表达式，而不是像“苏格拉底是人”这样的命题，其中“存在”是一个量词，而x是一个变量。
  • 意义：这将它与命题逻辑区分开来，命题逻辑不使用量词或关系; 在这个意义上，命题逻辑是一阶逻辑的基础。

逻辑推理

  • 存在一个数 = 存在最小的
逻辑悖论导致的
  • 毕导爱拖更”和“毕导不爱拖更”同时成立1
  • 因为“毕导爱拖更”为真 “毕导爱拖更”或“黎曼猜想成立”必为真
  • “毕导爱拖更”、“黎曼猜想成立”至少有一个为真
  • 又因为“毕导不爱拖更”为真 所以前半句不成立，故“黎曼猜想成立”为真，证毕。

基本概念

  1. 逆否命题：命题 "如果 P，则 Q"，其逆否命题是 "如果 非Q，则 非P"。逆否命题等价于原命题，当且仅当原命题的结构为蕴含式（implication）形式，即 "如果 P，则 Q"的If-Then 结构
  2. 存在量词与任意量词之间的转化： \(\((\exist x \sim Hx) \iff (\sim \forall x Hx)\)\) \(\((\sim \exist x Hx) \iff ( \forall x \sim Hx)\)\)

代数结构

在抽象代数里，代数结构（algebraic structure）是指装备了一个及以上的运算（最一般地，可以允许有无穷多个运算）的非空集合。一般研究的代数结构有群、环、域、格、模、域代数和向量空间等等。在数学中，更具体地说，在抽象代数中，代数结构是一个集合(称为载体集或底层集合)，它在它上定义了一个或多个满足公理的有限运算。

GPT: 群，环，域区别
  1. 群：
  2. 定义： 群是一个集合，其中有一个二元运算（通常是加法或乘法），满足封闭性（运算的结果仍在集合内）、结合律、存在单位元素（对于加法是0，对于乘法是1）和每个元素都有逆元素。

  3. 例子： 整数集合与加法形成一个群，因为整数的加法满足上述条件。

  4. 环：

  5. 定义： 环是一个集合，其中有两个二元运算（通常是加法和乘法），满足封闭性、结合律、存在加法单位元素、存在加法逆元素、乘法分配律。
  6. 在环中，乘法逆元素对于0是未定义的。也就是说，在环中，存在一个乘法逆元素的元素不能为0。环的乘法可以有逆元素，但不要求对所有非零元素都有。

  7. 例子： 整数集合与加法和乘法形成一个环，因为整数的加法和乘法满足上述条件。

  8. 域：

  9. 定义： 域也是一个集合，其中有两个二元运算（通常是加法和乘法），满足封闭性、结合律、存在加法和乘法单位元素、存在加法逆元素、存在乘法逆元素、乘法分配律。额外的，域要求乘法逆元素对于0是未定义的。
  10. 在域中，每个非零元素都必须有乘法逆元素。换句话说，对于域中的任何非零元素，都存在一个元素与之相乘得到域中的乘法单位元素（通常是1）。
  11. 域是环的一种特殊情况，区别在于域要求乘法逆元素对于所有非零元素都是定义的。
  12. 例子： 实数或复数集合与加法和乘法形成一个域，因为它们的加法和乘法满足上述条件。

简而言之，这些结构是数学中用来研究运算规则和性质的工具。在计算机学习中，这些抽象概念可以用来建模和解决各种问题，例如在优化算法、密码学、图形学等领域。如果有具体的问题或关注的方面，请告诉我，我将尽力提供更详细的解释。

需要进一步的研究学习

暂无

遇到的问题

暂无

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

秋招，百度的高铁柱面试官说，定义问题是很关键的一件事。能不能形式化的定义。（我已经很久没有注意这件事了，确实很重要。

参考文献

  1. 【毕导】这个视频里说的都是真的，但你却永远无法证明 ↩↩↩↩↩↩

  2. wiki First-order logic ↩↩↩

Thread and Process

线程的创建

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

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

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

示例代码： 

#include <iostream>
#include <thread>

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

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

std::thread t(threadFunction); 子线程会立刻执行

使用 std::thread 创建的子线程会立刻开始执行。具体来说，当你创建 std::thread 对象并将函数或可调用对象传递给它时，线程会立即开始执行你传递的函数或代码块。

例如，以下代码中的子线程会在创建后立即执行 threadFunction：

#include <iostream>
#include <thread>

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

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

在这段代码中，一旦执行到 std::thread t(threadFunction); 这行代码，子线程会立刻开始执行 threadFunction。主线程则继续执行后面的代码。在调用 t.join(); 之前，主线程和子线程是并行执行的。

需要注意的是，如果不调用 t.join();，主线程可能会在子线程完成之前就结束，从而导致子线程的输出可能不会被看到。因此，通常会使用 join() 来确保主线程等待子线程执行完毕。

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

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

示例代码： 

#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> 头文件。

示例代码： 

#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库。

示例代码： 

#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上的示例代码： 

#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. 当多个线程同时访问和修改同一个全局变量时，可能会发生数据竞争（race condition），导致不可预测的结果。
  5. 线程安全：
  6. 如果全局变量被多个线程访问，需要确保对这些变量的访问是线程安全的。这通常通过使用互斥锁（mutexes）、读写锁（read-write locks）、原子操作（atomic operations）或其他同步机制来实现。
  7. 可见性：
  8. 在某些情况下，一个线程对全局变量的修改可能不会立即对其他线程可见。这与处理器缓存、编译器优化以及内存屏障（memory barriers）的使用有关。
  9. 初始化：
  10. 全局变量的初始化在多线程环境中需要特别注意，以确保在任何线程访问变量之前，变量已经被正确初始化。

为了确保线程安全，可以使用互斥锁：

#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;
}

在这个同步版本中，我们使用 std::mutex 和 std::lock_guard 来确保每次只有一个线程可以修改全局变量，从而避免了数据竞争。

总之，虽然线程可以访问同一个全局变量，但必须小心处理并发访问，以确保程序的正确性和稳定性。

单例模式，全局(互斥锁)来监控，所有线程

要实现一个全局的 class 来统计进程中所有出现的线程的 TID，并为每个 TID 分配一个 CPU 核心，可以按照以下步骤进行设计。

  • 提供注册线程和分配核心的功能。
  • 提供一个静态实例，以确保全局唯一性。
#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. ThreadManager 类:

    • 采用了单例模式来确保全局唯一性。
    • registerThread() 函数用于在 threadMap_ 中注册线程的 TID 并分配核心号。
    • getCore() 函数用于获取特定 TID 的分配核心。

  2. 线程注册:

    • 在每个线程中调用 ThreadManager::getInstance().registerThread() 来注册线程的 TID 并分配核心。

常见相关代码

子线程的log单独输出到文件里

  • todo

子线程重命名, 与读取名字

#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;
}

线程亲和性设置

如何结合Host端和Device端的设计细节来高效线程调度

  • nvidia-smi等知道busID，
  • 使用类似 lspci -vv |grep "Processing a" -A 6 知道NUMA拓扑
  • numactl -H 看内存分布

鲲鹏920的环形总线结构

192核，分为8个node，每个node的24核又分为6个cluster，每个cluster的4个核为最小单元。

  • 简单测试: 使用taskset -c 0-4 {command},可以实现命令绑定在编号0-3核上。
  • 代码内实现: c++内通过pthread_setaffinity_np函数实现。
    • 绑定到NUMA node后，利用OS的自动CPU负载均衡即可。
将线程A绑定到一个核心上后，从这个线程创建出的子线程应该是会继承这个pthread_setaffinity_np的效果, 还有Thread name
  • htop -p pid 里 a 选项可以显示已有的亲和性设置
  • ps -p pid 可以看见CMD相同。

CPU负载均衡：线程的自动切换

线程在不同的 CPU 核之间切换是一种常见现象，这种行为被称为 CPU 负载均衡。它并不总是为了让线程变快，而是为了更好地管理系统资源和提高整体系统性能。以下是为什么会发生这种切换的原因：

  1. 负载均衡：
  2. 操作系统调度器 会尝试将 CPU 负载分布在所有可用的核心上，以防止某些核心过载或某些核心闲置。这种均衡有助于提高系统的整体性能和响应速度。

  3. 当一个核心的负载变得很高时，调度器可能会将一些线程移到其他较空闲的核心上执行，以平衡系统负载。

  4. 热管理：

  5. 多核处理器通常具有动态电源管理和温度控制机制。如果某个核心由于过度使用而变热，调度器可能会将线程切换到另一个较冷的核心，以避免过热并确保处理器稳定运行。

  6. 中断处理：

  7. 操作系统可能会将某些中断处理程序绑定到特定的核心上。当这些中断发生时，当前正在处理的线程可能会被暂停，并移到另一个核心继续执行。

  8. 资源竞争：

  9. 不同的核心共享某些资源（例如缓存、内存控制器等）。如果多个线程在同一个核心上运行，可能会导致资源争用。调度器可以通过在不同核心之间移动线程来减轻这种争用，从而提高性能。

  10. 调度策略：

  11. Linux 内核使用的调度策略（如 CFS：Completely Fair Scheduler）可能会认为在不同核心之间移动线程可以更公平地分配 CPU 时间片，从而提高系统的整体吞吐量。

是否会变快？线程在不同核心之间的切换本身不会让某个线程“变快”。相反，频繁的切换会引入一些开销（如缓存失效，线程状态切换等），在某些情况下甚至可能导致性能下降。

然而，通过均衡负载、管理热量和资源争用，操作系统调度器可以确保系统的稳定性和长时间运行时的性能一致性。因此，从全局来看，这种行为通常有利于提高系统的整体性能和响应能力，而不仅仅是单个线程的性能。

解决方法：如果你希望某个线程固定在一个核心上运行（避免在不同核心之间切换），可以使用 CPU 亲和性 来绑定线程到特定核心。但在大多数情况下，操作系统调度器会比手动绑定做得更好，除非你有非常特殊的性能要求。

使用 isolcpus 的内核设置可以隔离核心，但是这需要重启，有什么办法能不重启实现隔离吗

你可以使用 cset 工具来动态隔离 CPU 核心，而无需重启系统。cset（cpuset 的前端工具）允许你创建 CPU 和内存的分组，并将特定的任务分配到这些分组中，从而达到核心隔离的效果。以下是如何使用 cset 实现隔离的基本步骤：

  1. 安装 cset：

如果你的系统上还没有安装 cset，你可以使用包管理工具进行安装，例如在 Ubuntu 上：

sudo apt-get install cset
  1. 创建 CPU 集（cpuset）：

使用 cset 创建一个新的 CPU 集，比如将 CPU 2 和 3 隔离：

sudo cset set --cpu=2,3 --set=isolated
  1. 将任务分配到隔离的 CPU 集：

你可以将一个特定的任务（如进程 ID 或命令）绑定到刚才创建的 CPU 集中：

sudo cset proc --set=isolated --exec command

或者，如果你有一个运行中的进程，假设它的 PID 是 1234：

sudo cset proc --set=isolated --move 1234
  1. 查看当前 CPU 集：

你可以通过以下命令查看所有 CPU 集和任务的分配情况：

sudo cset set --list
  1. 移除 CPU 集：

如果你想恢复 CPU 核心的默认状态，可以删除创建的 CPU 集：

sudo cset set --destroy isolated

通过使用 cset，你可以在不重启系统的情况下灵活地管理 CPU 核心的分配和隔离。

请注意，cset 适用于需要较高实时性和性能隔离的应用场景。如果你的系统任务调度特别复杂，使用 cset 进行动态隔离可能需要更多的调试和配置。

Linux thread evaluation

Java uses lots of threads but threads have become significantly faster and cheaper with the NPTL in Linux 2.6.

pthread

to learn

父子线程进程的退出影响

http://originlee.com/2015/04/08/influence-of-main-threads-exiting-to-child-thread/

参考文献

无

  • 分类于 Tutorials
  • 需要 3 分钟阅读时间

ssh config & X11 & jump-machine

ssh config常见设置

Host node5
  HostName node5.xydustc.me   #或者ip
  IdentityFile ~/.ssh/id_rsa  #windows： "C:\Users\Administrator\.ssh\id_rsa"
  IdentitiesOnly yes          #IdentitiesOnly指定ssh只能使用配置文件指定的identity和certificate文件或通过ssh命令行通过身份验证，即使ssh-agent或PKCS11Provider提供了多个identities。
  User shaojiemike
  Port 22
  ProxyCommand E:\\commonSoftware\\Git\\mingw64\\bin\\connect.exe -S 127.0.0.1:7890 -a none %h %p
  # 注意ProxyCommand不能写全局，会代理其他ssh。出现ctrl-c会中断ssh连接之类的错误

Host *
   ForwardAgent yes     #是否将本地SSH代理转发到远程主机。如果设置为“yes”，则可以在远程主机上使用本地SSH代理，而无需在远程主机上设置新的SSH连接。
   AddKeysToAgent yes   #是否将私钥添加到ssh-agent中。如果设置为“yes”，则在使用ssh连接时，ssh客户端会自动将私钥添加到ssh-agent中。
   ForwardX11 yes
   ForwardX11Trusted yes
   Compression yes
   TCPKeepAlive=yes
   ServerAliveInterval 60 # Client每隔 60 秒发送一次请求给 Server，然后 Server响应，从而保持连接
   ServerAliveCountMax 3 # Client发出请求后，服务器端没有响应得次数达到3，就自动断开连接，正常情况下，Server 不会不响应

更安全但是更简单的加密 ed25519

Use new way

The error message "userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedAlgorithms [preauth]" indicates that the SSH server is configured to accept specific public key algorithms, and the client attempted to use the "ssh-rsa" algorithm, which is not included in the accepted algorithms list.

To resolve this issue, you have a few options:

  1. Update SSH Key Algorithm: If you are generating a new key pair, consider using a more secure algorithm such as Ed25519 instead of the older RSA algorithm.

    ssh-keygen -t ed25519 -f /path/to/output/keyfile -C "Your Comment Here"

  2. Update Server Configuration: If you don't have control over the client's key type, you may need to update the server's SSH configuration to include support for the "ssh-rsa" algorithm. Open the SSH server configuration file (usually located at /etc/ssh/sshd_config), and add or modify the following line:

    PubkeyAcceptedAlgorithms +ssh-rsa

    After making the change, restart the SSH server.

    sudo service ssh restart

    Note: Adding "ssh-rsa" might reduce the security of your SSH server, as RSA is considered less secure than some newer algorithms.

  3. Check Key Types: Ensure that you are using the correct key type when attempting to authenticate. If you are using an existing key, make sure it's the right type (e.g., Ed25519) and not RSA.

Choose the option that best fits your security requirements and constraints. If possible, it's generally recommended to use more modern and secure key algorithms like Ed25519 over older ones like RSA.

查看 ssh 日志

sudo journalctl -u ssh --since "yesterday" |less

X11 forward GUI

windows use mobaxterm, mac use xquartz + iterms

ssh -Y [email protected]

跳板机

目的

在管理外网服务器时，出于安全等因素的考虑，我们一般不会把所有服务器都设置成可ssh直连，而是会从中挑选出一台机器作为跳板机，当我们想要连接外网服务器时，我们要先通过ssh登录到跳板机，再从跳板机登录到目标服务器。

密钥认证

  1. 开启ssh-agent，然后将我们的private key添加到ssh-agent中。
$ eval $(ssh-agent)
Agent pid 8350
$ ssh-add
Identity added: /home/yt/.ssh/id_rsa (yt@arch)
Identity added: /home/yt/.ssh/id_ed25519 (yt@arch)
  1. ssh登录到跳板机（不过此次加上了-A参数，表示开启agent forwarding）。
ssh -A [email protected]

或者直接

ssh -J [email protected] [email protected]

这条命令将会首先连接到 [email protected] 的跳板机，然后再通过跳板机连接到 [email protected] 的目标服务器。

scp传递数据

scp -J [email protected] [email protected]:/path/to/source/file /path/to/destination/file

这个命令将会通过 [email protected] 的跳板机从源文件 /path/to/source/file 复制数据到 [email protected] 的目标文件 /path/to/destination/file。

config配置

Host <name>
    HostName 127.0.0.1 #是不是写错了??不是目标ip吗？
    User <user>
    Port <port>
    ProxyCommand ssh <cloud-user>@<cloud-host> -W %h:%p

//example
Host xunfei-V100
   HostName 172.31.97.164
   User root
   ProxyCommand C:\Windows\System32\OpenSSH\ssh.exe node1 netcat -w 120 %h %p

如何判断当前ssh没用跳板机

check is ssh use direct connect not use jump host

基于跳板机的x11转发

google check ssh gui x11 use jump host

https://www.ibm.com/support/pages/how-forward-x11-client-through-jump-host-back-pc-x-emulator

  1. server side
  2. /etc/ssh/sshd_config
    1. X11Forwarding yes
    2. X11UseForwarding yes
  3. install xauth
    1. environment variables on the server. DISPLAY and XAUTHORITY will automatically be set to their proper values.
    2. if DISPLAY is not set, it means ssh is not forwarding the X11 connection.
  4. client side
  5. ForwardX11 yes in ~/.ssh/config
    1. X11UseLocalhost yes
  6. ssh -v -X name@ip # -v for debug

使用跳板机转发 vscode

vlab 能正常登录的情况下ssh -i D:\\PowerShell\\vlab-vm7096.pem [email protected]

有两种设置ssh config设置方法

Host jumpSnode6Ipv4W
  Hostname 202.38.72.23
  User shaojiemike
  Port 22
  ProxyCommand C:\\Windows\\System32\\OpenSSH\\ssh.exe -W %h:%p -i D:\\PowerShell\\vlab-vm7096.pem ubuntu@vlab.ustc.edu.cn

Host jumpSnode6Ipv4
  Hostname 202.38.72.23
  User shaojiemike
  Port 22
  ProxyCommand C:\\Windows\\System32\\OpenSSH\\ssh.exe -i D:\\PowerShell\\vlab-vm7096.pem ubuntu@vlab.ustc.edu.cn netcat -w 120 %h %p

参考文献

https://cloud.tencent.com/developer/article/1501977

  • 分类于 Tutorials
  • 需要 6 分钟阅读时间

package manager: apt

基本概念

Ubuntu 版本代号

都是动物, 都是两个词，并且两个词的首字母相同,从6.06开始，首字母从D开始递增。

中间版本也有代号 Ubuntu 14.10 (Utopic Unicorn) 以及 Ubuntu 14.04.5 LTS (Trusty Tahr) 官网可以查看

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 20.04.5 LTS
Release:        20.04
Codename:       focal
各版本 代号

PPA（Personal Package Archive）

  • PPA 代表 个人包存档。
  • PPA 允许应用程序开发人员和 Linux 用户创建自己的存储库来分发软件。
  • 使用 PPA，您可以轻松获得更新的软件版本或无法通过官方 Ubuntu 存储库获得的软件。
  • 除了PPA之外，其他操作系统也有类似的概念，例如Debian的APT存储库、Fedora的DNF存储库等。

常见三板斧

sudo add-apt-repository ppa:dr-akulavich/lighttable
sudo apt-get update
sudo apt-get install lighttable-installer

DEB packages

DEB packages（Debian Binary Package）是Debian及其基于Debian的操作系统（如Ubuntu）中使用的软件包格式。它们是一种存档格式，包含软件的二进制文件、配置文件、依赖关系和其他必要的文件。DEB packages是一种用于软件分发和安装的标准格式。

  • 相比于PPA，大部分DEB的包没有source.list.不能自动更新。

repository

存储库是文件的集合，其中包含有关各种软件、其版本和其他一些详细信息（如校验和）的信息。每个 Ubuntu 版本都有自己的一套官方的四个存储库：

  • Main – Canonical-supported free and open-source software. 规范支持的免费和开源软件。
  • Universe – Community-maintained free and open-source software. 社区维护的自由和开源软件。
  • Restricted – Proprietary drivers for devices. 设备的专有驱动程序。
  • Multiverse – Software restricted by copyright or legal issues. 受版权或法律问题限制的软件。

Ubuntu 添加软件源

换源操作官方教程和官方软件源

清华教程或者科大教程

sudo nano /etc/apt/sources.list
# add link
# ctrl+X y enter保存

清空缓存

sudo apt clean && sudo apt autoclean
sudo apt-get update /autoremove /upgrade

PPA vs repository

to read： https://itsfoss.com/ppa-guide/

实践

Ubuntu20.04 install old gcc4.8

寻找支持gcc-4.8的apt源，也就是xenial版本的一个源。

vim /etc/apt/sources.list

deb http://dk.archive.ubuntu.com/ubuntu/ xenial main
deb http://dk.archive.ubuntu.com/ubuntu/ xenial universe

sudo apt update
//会显示 Get:54 http://dk.archive.ubuntu.com/ubuntu xenial/main i386 Packages [1,196 kB]
sudo apt install gcc-4.8

Ubuntu20.04 install new glibc-2.35

Ubuntu 22.04 有对应的 glibc

deb https://mirrors.ustc.edu.cn/ubuntu/ jammy main restricted universe multiverse

原本的思路是安装gcc-11, 结果发现glibc需要增量安装。需要在node5进行测试。

Unpacking libc6:i386 (2.35-0ubuntu3) over (2.31-0ubuntu9.9) ...
Preparing to unpack .../6-libselinux1_3.3-1build2_amd64.deb ...
De-configuring libselinux1:i386 (3.0-1build2) ...
Unpacking libselinux1:amd64 (3.3-1build2) over (3.0-1build2) ...
tar: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.33' not found (required by /lib/x86_64-linux-gnu/libselinux.so.1)
tar: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.34' not found (required by /lib/x86_64-linux-gnu/libselinux.so.1)
dpkg-deb: error: tar subprocess returned error exit status 1
dpkg: error processing archive /tmp/apt-dpkg-install-b0waQ0/7-libselinux1_3.3-1build2_i386.deb (--unpack):
 dpkg-deb --control subprocess returned error exit status 2
tar: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.33' not found (required by /lib/x86_64-linux-gnu/libselinux.so.1)
tar: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.34' not found (required by /lib/x86_64-linux-gnu/libselinux.so.1)
dpkg-deb: error: tar subprocess returned error exit status 1
dpkg: error processing archive /tmp/apt-dpkg-install-b0waQ0/8-libc-bin_2.35-0ubuntu3_amd64.deb (--unpack):
 dpkg-deb --control subprocess returned error exit status 2
Errors were encountered while processing:
 /tmp/apt-dpkg-install-b0waQ0/4-libc6_2.35-0ubuntu3_amd64.deb
 /tmp/apt-dpkg-install-b0waQ0/7-libselinux1_3.3-1build2_i386.deb
 /tmp/apt-dpkg-install-b0waQ0/8-libc-bin_2.35-0ubuntu3_amd64.deb
/usr/bin/dpkg: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.33' not found (required by /lib/x86_64-linux-gnu/libselinux.so.1)
/usr/bin/dpkg: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.34' not found (required by /lib/x86_64-linux-gnu/libselinux.so.1)
/usr/bin/gdbus: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.33' not found (required by /lib/x86_64-linux-gnu/libselinux.so.1)
/usr/bin/gdbus: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.34' not found (required by /lib/x86_64-linux-gnu/libselinux.so.1)
E: Sub-process /usr/bin/dpkg returned an error code (1)
E: Sub-process dpkg --set-selections returned an error code (1)
E: Couldn't revert dpkg selection for approved remove/purge after an error was encountered!

Install newest gcc

https://gist.github.com/application2000/73fd6f4bf1be6600a2cf9f56315a2d91

update-alternatives 设置软件版本

sudo update-alternatives --install /usr/bin/clang clang /usr/bin/clang-6.0 1 --slave /usr/bin/clang++ clang++ /usr/bin/clang++-6.0
sudo update-alternatives --install /usr/bin/clang clang /usr/bin/clang-10 1 --slave /usr/bin/clang++ clang++ /usr/bin/clang++-10
sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-4.8 20

将某个版本加入gcc候选中，最后的数字是优先级.

运行下面命令切换

sudo update-alternatives --config gcc

代理 apt-get

apt不能使用export http_proxy的代理，需要额外设置

临时设置

如果只是暂时设置代理，一次性使用：

sudo -E http_proxy="http://proxy.example.com:port" apt-get update

# or -o 'xxx'
sudo apt -o Acquire::https::proxy="http://<proxy-url>:<port>/" update
sudo apt-get -o Acquire::http::proxy="http://<proxy-url>:<port>/" update

永久设置

Or add lines in /etc/apt/apt.conf 

Acquire::http::proxy "http://<proxy>:<port>/";
Acquire::ftp::proxy "ftp://<proxy>:<port>/";
Acquire::https::proxy "https://<proxy>:<port>/";

Acquire::http::proxy "http://127.0.0.1:7233/";
Acquire::ftp::proxy "ftp://127.0.0.1:7233/";
Acquire::https::proxy "https://127.0.0.1:7233/";

This was the reason why you could reach proxy but couldn't get past it, since there is no username password information. So just put that info into it.

Acquire::http::proxy "http://<username>:<password>@<proxy>:<port>/";
Acquire::ftp::proxy "ftp://<username>:<password>@<proxy>:<port>/";
Acquire::https::proxy "https://<username>:<password>@<proxy>:<port>/";

save the file and you are done...

TIP: More better add these lines in another file, /etc/apt/apt.conf.d/80proxy. This will ensure that after a version upgrade changes won't be lost.

Could not handshake: The TLS connection was non-properly terminated. 
Err:3 https://swupdate.openvpn.net/community/openvpn3/repos focal Release
Could not handshake: The TLS connection was non-properly terminated. [IP: 127.0.0.1 7233]
  • 直接将Acquire::https::proxy "https://<proxy>:<port>/";
  • 改成Acquire::https::proxy "http://<proxy>:<port>/";

有时候代理也解决不了，就只能手动安装deb包

可以参考jellyfin的教程

问题

E: Could not open lock file

shaojiemike@snode6 ~/github/llvm-3.5/llvm-project  [01:59:12]
> apt update
Reading package lists... Done
E: Could not open lock file /var/lib/apt/lists/lock - open (13: Permission denied)
E: Unable to lock directory /var/lib/apt/lists/
W: Problem unlinking the file /var/cache/apt/pkgcache.bin - RemoveCaches (13: Permission denied)
W: Problem unlinking the file /var/cache/apt/srcpkgcache.bin - RemoveCaches (13: Permission denied)

sudo 解决, or sudo rm /var/lib/apt/lists/lock

etcd start fail 
See "systemctl status etcd.service" and "journalctl -xe" for details.
invoke-rc.d: initscript etcd, action "start" failed.
● etcd.service - etcd - highly-available key value store
Loaded: loaded (/lib/systemd/system/etcd.service; disabled; vendor preset: enabled)
Active: failed (Result: exit-code) since Thu 2024-09-05 22:21:44 EDT; 10ms ago
    Docs: https://github.com/coreos/etcd
        man:etcd
Process: 71732 ExecStart=/usr/bin/etcd $DAEMON_ARGS (code=exited, status=1/FAILURE)
Main PID: 71732 (code=exited, status=1/FAILURE)

Sep 05 22:21:43 huawei systemd[1]: Starting etcd - highly-available key value store...
Sep 05 22:21:44 huawei etcd[71732]: etcd on unsupported platform without ETCD_UNSUPPORTED_ARCH=arm64 set.
Sep 05 22:21:44 huawei systemd[1]: etcd.service: Main process exited, code=exited, status=1/FAILURE
Sep 05 22:21:44 huawei systemd[1]: etcd.service: Failed with result 'exit-code'.
Sep 05 22:21:44 huawei systemd[1]: Failed to start etcd - highly-available key value store.
dpkg: error processing package etcd-server (--configure):
installed etcd-server package post-installation script subprocess returned error exit status 1
dpkg: dependency problems prevent configuration of etcd:
etcd depends on etcd-server; however:
Package etcd-server is not configured yet.

dpkg: error processing package etcd (--configure):
dependency problems - leaving unconfigured
Setting up zsh (5.4.2-3ubuntu3.2) ...
No apport report written because the error message indicates its a followup error from a previous failure.
                                                                                                        Processing triggers for man-db (2.8.3-2ubuntu0.1) ...
Errors were encountered while processing:
etcd-server
etcd
E: Sub-process /usr/bin/dpkg returned an error code (1)

这个错误的主要原因是 etcd 尝试在不受支持的架构上运行（即 arm64），并且你没有设置环境变量 ETCD_UNSUPPORTED_ARCH=arm64 来强制 etcd 运行。因此，etcd 服务启动失败。

要解决这个问题，你可以尝试以下步骤：

  1. 设置环境变量 ETCD_UNSUPPORTED_ARCH=arm64

编辑 etcd.service 的配置文件，使其在启动时包含该环境变量。

  1. 打开 /lib/systemd/system/etcd.service： 

    sudo nano /lib/systemd/system/etcd.service

  2. 在 [Service] 部分添加以下行： 

    Environment="ETCD_UNSUPPORTED_ARCH=arm64"

  3. 保存并关闭文件。

  4. 重新加载 systemd 配置并启动 etcd

完成修改后，执行以下命令来重新加载 systemd 配置并启动 etcd：

sudo systemctl daemon-reload
sudo systemctl start etcd
  1. 检查服务状态

检查 etcd 服务是否正常启动：

sudo systemctl status etcd
  1. 查看日志

如果 etcd 服务仍未启动，可以查看 journalctl 以获取详细日志：

journalctl -xe

这些步骤应该能帮助你解决 etcd 服务在 arm64 架构上的启动问题。如果问题仍然存在，日志可能会提供进一步的线索。

参考文献

https://blog.csdn.net/feinifi/article/details/121793945