秋招了，写点计算机八股笔记，方便自己背诵和复习
欢迎门友补充、提问，或者在楼中写下自己认为的重要八股知识
9 Likes
浅拷贝，深拷贝，std::move
- 浅拷贝：按字节直接复制，可以解决很多场景的问题，但是当被拷贝的对象中含有指针或文件描述符时，会出现以下两方面的错误：
- 使用的时候，被拷贝对象和拷贝对象的指针指向同一个地址，一方的改动会影响另一方的使用，这往往是不符合需要实现的逻辑的。
- 析构的时候，被拷贝对象和拷贝对象的指针均被析构，则会对同一个地址析构两次，UB。
- 深拷贝：用来解决上述浅拷贝会出现的错误，深拷贝需要手动实现（赋值运算符/构造函数），假设被拷贝对象中有一个指针，则申请一段新的内存，复制被拷贝对象指针指向的内容到这段新的内存上。这样被拷贝对象和拷贝对象将会互不干扰。
- std::move：将左值转换为右值，其意义大概类似于
template<typename T>
T && move(T lvalue) {
return static_cast<T &&>(lvalue);
}
原始代码中略有更改，涉及到一些模板语法糖，不再赘述。使用 a = std::move(b);可以实现移动语义，也即对象所有权的转移，移动后 b 的值回到初始化状态（往往由移动构造/赋值函数来决定具体如何初始化，可见下例），不能再继续使用，但是可以被析构。
使用如下代码来实现移动构造函数和移动赋值函数
class A{
public:
A() : data(nullptr) {
}
A(int value) : data(new int(value)) {
}
A(A&& other): data(other.data) {
other.data = nullptr;
}
A& operator=(A&& other) {
if (this != &other) {
delete data;
data = other.data;
other.data = nullptr;
}
return *this;
}
~A() {
delete data;
}
private:
int *data;
};
2 Likes
lambda 表达式
使用方法：
int x= 10;
auto f = [x](int c = 5) {return x + c;};
std::cout << f() << std::endl;
中括号内参数为捕获列表，可有如下几种填入方式：
小括号内为形参列表，使用方式类似函数
如需更改 x 的值，则需要加上 mutable 关键字，如下：
int x= 10;
auto f = [&x](int c = 5) mutable {x=c;};
f();
std::cout << x << std::endl;
1 Like
虚函数和 CRTP 实现函数多态
虚函数：
class A{
public:
virtual void print() {
puts("A");
}
};
class B: public A{
public:
void print() {
puts("B");
}
};
class C: public A{
public:
void print() {
puts("C");
}
};
int main() {
B x;
A y = static_cast<A>(B);
y.print();
}
坏处：
- 内存上比 CRTP 多一个虚表指针
- 运行时比 CRTP 多一次指针跳转
- 函数无法内联，短函数情况下性能影响很大
- 代码可预测性低，不利于 Prefetch 和间接分支预测
CRTP：
template<typename der>
class A{
public:
void print() {
static_cast<der *>(this)->printName();
}
void printName() {
puts("A");
}
};
class B: public A<B>{
public:
void printName() {
puts("B");
}
};
class C:public A<C>{
public:
void printName() {
puts("C");
}
};
template<typename der>
void CRTP(A<der>& x) {
x.print();
}
int main() {
B x;
CRTP(x);
}
坏处：
- 代码逻辑更复杂，不利于阅读
- 不能实现动态派发
1 Like
指令乱序执行与内存屏障
指令乱序执行：
体系结构课上讲了很多（比如记分牌算法和 Tomasulo 算法），直接上网粘贴一段
乱序处理器（Out-of-order processors）处理指令通常有以下几步：
- 指令获取
- 指令被分发到指令队列
- 指令在指令队列中等待，直到输入操作对象可用（一旦输入操作对象可用，指令就可以离开队列，即便更早的指令未被执行）
- 指令被分配到适当的功能单元并执行
- 执行结果被放入队列（而不立即写入寄存器堆）
- 只有所有更早请求执行的指令的执行结果被写入寄存器堆后，指令执行的结果才被写入寄存器堆（执行结果重排序，让执行看起来是有序的）
从上面的执行过程可以看出，乱序执行相比有序执行能够避免等待不可用的操作对象（有序执行的第二步）从而提高了效率。现代的机器上，处理器运行的速度比内存快很多，有序处理器花在等待可用数据的时间里已经可以处理大量指令了。
内存屏障分为两类：
- 编译器屏障
用 volatile 关键字来定义变量，volatile 关键字有三重含义：
- volatile 变量之间的访问顺序不会被编译器改变
- volatile 变量每次读取时均访问内存
- volatile 变量不会被编译器进行激进优化
举例：
//thread1
volatile bool tag = true;
volatile int x = 0;
while(tag);
work(x)
//thread2
x = 10;
tag = false;
这里 thread1 进入死循环，thread2 将 x 变为 10 写回内存，再 tag 变为 false 后写回内存，thread1 从内存中取到 tag，循环停止，调用 work(10)。
假设不使用 volatile 变量，编译优化可能出现内存乱序执行，例如 thread2 中 x=10 后于 tag=false 执行，就有可能导致 thread1 执行 work(0)。
- CPU 屏障
保证读写操作有序的，mb() 和 smp_mb()
仅保证写操作有序的，wmb() 和 smp_wmb()
仅保证读操作有序的，rmb() 和 smp_rmb()
在多核处理机上实现使用的内存屏障，此时仅使用编译器屏障不够，具体涉及到缓存一致性，先按下不表。
缓存一致性与内存屏障
MESI 缓存一致性协议：
一个双核处理器如上图，memory 可以是主存，也可以是 L3 Cache（往往是 L3 Cache）
两个 Cache 指 L1/L2 Cache，简单起见假设只有一层 Cache。
考虑如下场景：
有一个变量 x=0，存在于 memory 和 CPU0 的 Cache 中
- CPU1 read x，Cache miss，向 memory 请求得到 x 数据并存储进 Cache 中
- CPU0 write x=1，Cache hit，直接在 CPU0 的 Cache 中修改，如果 Cache 不是写穿透策略则 memory 中 x 仍然为 0
- CPU1 read x，Cache hit，读取 x=0，发生错误
为了防止上述情况发生，使用 MESI 协议来维护缓存一致性。
MESI 协议有四个状态，分别如下：
I: Invalidate，Cacheline 的数据是无效的。
S: Shared，Cacheline 是最新的，且至少一个其他核心的 Cache 中也存在该 Cacheline。
M: Modified，Cacheline 是最新的且和主存不一致，其他核心的 Cache 中不存在该 Cacheline 的最新副本。
E: Exclusive，Cacheline 是最新的且和主存一致，其他核心的 Cache 中不存在该 Cacheline 的最新副本。
考虑维护上述状态，根据 CPU 的各种行为形成了一个四状态自动机，进行 trans 的时候需要各个核心之间完成信息交互。
可能发生的交互消息类型：
Read: 读取 Cache miss 时，发送该消息，从其他核心的 Cache 或者主存中获取最新副本，消息内容为读取的数据地址。
Read Response: Read 的响应信号，消息内容为对应数据的最新副本。
Invalidate：收到消息的 Cache 要将对应数据的 Cacheline 无效化，消息内容为无效化的数据地址。
Invalidate Ack: Invalidate 的响应信号，在无效化相应 Cacheline 后返回 Ack。
Read Invalidate: 读取该 cacheline 的最新数据，并将核心 Cache 中的相应 cacheline 无效化。消息内容为读取和无效化的数据地址。一般在发生写 Cache miss 的时候发送此信号。需要收到 read response 和 invalidate acknowledge 信号作为响应。
Writeback: 发生在处于 M 状态的 Cacheline 被替换时，将脏数据块写回主存。消息内容为数据地址和 Cacheline 的副本。
MESI 协议很正确，但是效率并不高，不过可以增加一些简单优化，Store Buffer和Invalidate Queue
上图为 Arm 架构，x86 架构没有 Invalidate Queue
Store Buffer
当 CPU 发生写缺失时，需要发送 Read Invalidate 并等待响应，这一过程可能需要相当长的时间，而在这一时间段内，CPU 不能做其他事情，严重影响性能。使用 store buffer 解决这一问题。如下图所示，CPU 在发生写缺失时，可以发送 read invalidate 信号，同时将要写的数据存储到 store buffer 中，然后继续执行后面的指令。等到其他 CPU 或者主存返回了最新数据，同时接受到所有 CPU 的 invalidate ack 信号后，再将数据从 store buffer 中读出，写入 Cache 中。
Store Forwarding
考虑如下场景：
起初 x=0 且存在于 CPU 的 Cache 中
- CPU 向 cache 中写入 x=1，则 CPU 会写操作存储到 store buffer 中，并发起 invalidate 操作。
- CPU 读取 x，此时即 x=1 仍存储在 store buffer 中，没有修改成功。由于在 cacheline 中命中，得到 x=0。
Store Forwarding：当 CPU 读取数据时，首先检查 store buffer 中是否存在该数据，若存在，直接读取该数据，若不存在，再从 cache 中读取。
Store Buffer 与内存屏障
假设上述代码中删去第四行的 smp_mb()，考虑让 thread0 在 CPU0 上执行 foo 函数，thread1 在 CPU1 上执行 bar 函数。
初始时刻，a 的副本仅存储在 CPU1 的 Cache 中，b 的副本仅存储在 CPU0 的 Cache 中，则考虑如下执行顺序：
- cpu0 执行 a=1，由于 a 不在 cpu0 的 cache 中，因此 cpu0 会发起 read invalidate 信号，同时将 a=1 存储在 store buffer 中。
- cpu1 执行 while(b==0)，由于 b 不在 cpu1 的 cache 中，因此 cpu1 会发送 read 信号，请求 b 的最新副本。
- cpu0 执行 b=1，由于 b 在 cpu0 的 cache 中，因此直接 hit，将 b 的值改写为 1 即可。
- cpu0 收到来自 cpu1 的 read 信号，此时，cpu0 将 b 的新值 1 返回给 cpu1 即可。
- cpu1 收到 b 的新值 1，cpu1 收到 b 的新值 1 后，将其更新到 cacheline 中，同时由于 b=1，因此 cpu1 跳出 while 循环。
- cpu1 执行 assert(a==1)，发现此时 a 的值为 0，断言失败。
- cpu1 收到 read invalidate 信号，将数据返回给 cpu0，同时无效 a 所在 cacheline。但此时已经太晚了！
smp_mb() 的作用是将 Store Buffer 中的内容被刷新到 Cache，也即阻塞至所有在该句话之前的 store 对所有 CPU 可见。
Invalidate Queues
Cache 的 Store Buffer 往往很小，当 Store Buffer 写满时，CPU 必须等待某一个 Store Buffer 中的内容被刷出，再 push 新的 store 指令进入，会导致性能大大降低。Store Buffer 内容的刷出速度取决于 Invalidate Ack 指令的回复速度。
CPU 收到 Invalidate 信号后，先不 Invalidate，而是将所有 Invalidate 信息存入 Invalidate Queue，然后提前返回 Invalidate Ack。Invalidate Queue 会异步地对 Cacheline 进行无效化。
Invalidate Queues 和内存屏障
考虑如下场景：
CPU1 和 CPU2 的 Cache 中同时持有 x=0 的最新副本，Cacheline 状态为 Shared。
考虑按照如下顺序执行指令：
- CPU1 write x=1，发送 Invalidate 信号，将写信号放入 store buffer。
- CPU2 收到 Invalidate 信号后返回 Invalidate Ack。
- CPU1 的 store buffer 收到 Invalidate Ack，将 x=1 写入 Cache。
- CPU2 read x，此时 CPU2 检测到 Cache 中对应 Cacheline 的状态为 Shared，直接读出 x=0（读取结果错误）
- CPU2 的 Cache 将 x 所在 Cacheline 的状态改为 Invalidate，同时从 Invalidate Queue 中 pop 出该条指令，但为时已晚。
可以仍然考虑使用 smp_mb()，将 Invalidate Queue 中的内容清空，也即阻塞至所有在该句话之前的 load 对所有 CPU 可见。
关于内存屏障的思考
综上所述，其实我们可以发现，读写屏障 mb() 其实就是既清空 Store Buffer 和 Invalidate Queue，单独的写屏障 wmb() 可能是清空 Store Buffer，单独的读屏障 rmb() 还没有想清楚是怎么实现的。
预处理
- 展开所有宏定义，条件宏定义
- 将#include 包含的头文件插入到指定位置
- 删除注释，添加文件名和行号（用于报错）
编译
编译过程可分为 6 步：词法分析，语法分析，语义分析，源代码优化，代码生成，目标代码优化
前 4 步属于编译器前端，后 2 步属于编译器后端，按照中间语言生成的前后来划分。
具体来说，词法分析将代码分割为 token，语法分析通过 token 产生抽象语法树，语义分析对抽象语法树进一步处理，检查程序是否符合语义规则，源代码优化将整个抽象语法树转换为中间代码。
汇编
汇编器将 a.s 翻译成机器语言指令，并将这些指令打包为可重定位目标文件（也就是.o 文件）。
链接
可重定位目标文件
其格式和内容如下：
----------------------
| ELF Head | ELF 头，描述目标文件的基本信息
----------------------
| .text | 机器代码
----------------------
| .rodata | 只读数据
----------------------
| .data | 已初始化的全局变量和静态变量
----------------------
| .bss | 未初始化的全局变量和静态变量（实际上不占用空间，只需要运行时赋初值）
----------------------
| .symtab | 符号表，存储定义和引用的所有函数和全局变量
----------------------
| .rel.text | 代码重定位表，调用外部函数的指令需要重定位
----------------------
| .rel.data | 数据重定位表，引用外部全局变量和外部函数的全局变量需要重定位
----------------------
| .debug |
----------------------
| .line |
----------------------
| .strtab |
----------------------
|section header table|
----------------------
静态链接
- 链接器获取各个目标文件的符号表，并将之合并为一个全局符号表。
- 链接器获取各个目标文件的各个段的长度，计算出每个合并后段的长度与位置。
- 每个段的起始位置都默认是 0，加载时通过段起始地址 + 段内偏移量访问字段。
- 符号解析
每个可重定位目标文件中都有三类符号：
a. 被当前模块定义且不能被其他模块引用的符号（static 函数和全局变量）
b. 被当前模块定义且能被其他模块引用的符号（不带 static 的函数和全局变量）
c. 被当前模块引用但在其他模块内定义的符号（其他模块定义的不带 static 的函数和全局变量）
将每一个符号引用指向其对应的符号定义，就是符号解析，符号解析的规则如下：
强符号是给定初值且定义的符号，弱符号是声明但未定义的符号。
a. 只能有一个强符号。
b. 一个强符号和多个弱符号，选择强符号为符号定义。
c. 多个若符号，没有强符号，选择任意一个弱符号为符号定义。 - 重定位
上述生成的文件中，各个段的起始位置都默认是 0，链接器需要把符号定义和内存对应，这一对应的过程就是重定位。
a. 链接器首先把各个段合并，生成聚合段作为可执行目标文件的段
b. 计算出每个段的长度和起始位置
c. 根据每个段的起始位置，给每个段内的代码/符号引用赋以运行时地址（也即段内偏移量）
3.静态链接的优缺点
静态链接优缺点
缺点：浪费空间，因为每个可执行程序中对所有需要的目标文件都要有一份副本；更新困难，每次修改库函数代码，就需要重新编译链接。
优点：在可执行程序中具备了执行程序需要的任何东西，执行时运行速度快。
动态链接
动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在运行时完成链接。
假设现在有两个程序 program1.o 和 program2.o，这两者共用同一个库 lib.o，假设首先运行程序 program1，系统首先加载 program1.o，当系统发现 program1.o 中用到了 lib.o，即 program1.o 依赖于 lib.o，那么系统接着加载 lib.o，如果 program1.o 和 lib.o 还依赖于其他目标文件，则依次全部加载到内存中。当 program2 运行时，同样的加载 program2.o，然后发现 program2.o 依赖于 lib.o，但是此时 lib.o 已经存在于内存中，这个时候就不再进行重新加载，而是将内存中已经存在的 lib.o 映射到 program2 的虚拟地址空间中，从而进行链接（这个链接过程和静态链接类似）形成可执行程序。
动态链接的加载时重定位
- 重定位.so 的文本和数据到某个内存段。
- 重定位可执行文件中所有对.so 文件的引用。
这里涉及到一个有趣的细节，在 ics 课编码 linker 的时候，引用动态链接库中的符号会在第一次引用时多次跳转指针找到对应符号的内存段，并记录下来具体的位置，而在第二次引用时，则使用第一次记录下来的具体位置直接访问。
动态链接优缺点
优点：即使需要每个程序都依赖同一个库，也不会像静态链接那样在内存中存在多个副本，而是这多个程序在执行时共享同一份副本；更新方便，只需要替换原来的库文件，而无需将所有的程序重新链接。
缺点：链接推迟到了运行时，损失性能。
加载
通过加载器将可执行文件的代码和数据从磁盘中复制到内存中，然后 PC 跳转到程序的第一条指令或入口点。
2 Likes
原子操作和原子类型
std::atomic
在 atomic 库中定义了原子类型 std::atomic<>，例如可以使用 std::atomic。
std::atomic<>可以通过函数实现各类原子操作，例如 std::atomic<>::load()，std::atomic<>::store()，std::atomic<>::fetch_and()，std:;atomic<>::fetch_add 等等。
CAS 操作
通过 atomic<>::compare_exchange_weak/strong(x, y) 函数实现。表示如果原子量的值等于 x，则令原子量的值变为 y，且返回 true，否则将 x 的值变为原子量的值且返回 false。
weak 性能更好，但是可能在可以返回 true 的时候返回 false。
strong 性能更差，但是在可以返回 true 的时候一定会返回 true。
C++ 内存序
- seq_cst 要求所有原子操作必须按照在程序中出现的顺序执行，最严格的内存序
- acquire 确保之前的所有使用 release 的写操作都对当前线程可见，该语句后的所有语句不能先于当前语句执行完成前执行。
- release 确保该语句前的所有写语句都已经执行完毕，并且对其他线程可见。
- acq_rel 确保该语句后的读语句执行前，该语句前的所有写语句执行完毕且对其他线程可见；确保该语句后的写语句执行前，该语句前的所有读语句执行完毕。
- relaxed 不对顺序做限制，最弱的内存序。
- consume
1 Like
pthread(POXIS thread)
互斥锁和自旋锁
Mutex 想要使用 lock 去获得一个锁的时候，如果此时这个锁正被其他线程持有，那么使用 lock 的线程就会被阻塞，进行上下文切换，将线程放置到等待队列中。此时 CPU 可以被安排去做其他事情，等待锁的所有权空出来后再再次执行该线程。
Spin 想要使用 lock 获得一个锁的时候，如果此时无法获取到锁，会一直忙等待，直到获取该锁为止。
具体来说，一般获取锁的等待时间较长的时候使用 Mutex，获取锁的等待时间较短的时候使用 Spin。
条件变量
std::condition_variable
使用函数：
-
pthread_cond_init/destroy 类似于互斥锁和自旋锁
-
pthread_cond_wait
函数定义：
int pthread_cond_wait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex)
cond：指向条件变量的指针。
mutex：指向互斥锁的指针。
调用该函数之前，必须先获得互斥锁 mutex，在等待期间，互斥锁会自动释放，并使当前线程处于阻塞状态，直到条件变量被唤醒并且重新获得互斥锁为止。 -
pthread_cond_signal/broadcast
用于唤醒等待条件变量的一个线程。signal 如果有多个线程在等待条件变量，则会唤醒其中一个线程；broadcast 则是唤醒所有等待的线程。
如果没有线程在等待条件变量，则该函数不会产生任何效果。
阻塞式循环队列
上网抄个代码：
#include <unistd.h>
#include <cstdlib>
#include <condition_variable>
#include <iostream>
#include <mutex>
#include <thread>
static const int kItemRepositorySize = 10; // Item buffer size.
static const int kItemsToProduce = 1000; // How many items we plan to produce.
struct ItemRepository {
int item_buffer[kItemRepositorySize]; // 产品缓冲区，配合 read_position 和 write_position 模型环形队列.
size_t read_position; // 消费者读取产品位置.
size_t write_position; // 生产者写入产品位置.
std::mutex mtx; // 互斥量，保护产品缓冲区
std::condition_variable repo_not_full; // 条件变量，指示产品缓冲区不为满.
std::condition_variable repo_not_empty; // 条件变量，指示产品缓冲区不为空.
} gItemRepository; // 产品库全局变量，生产者和消费者操作该变量.
typedef struct ItemRepository ItemRepository;
void ProduceItem(ItemRepository *ir, int item)
{
std::unique_lock<std::mutex> lock(ir->mtx);
while(((ir->write_position + 1) % kItemRepositorySize)
== ir->read_position) { // item buffer is full, just wait here.
std::cout << "Producer is waiting for an empty slot...\n";
(ir->repo_not_full).wait(lock); // 生产者等待"产品库缓冲区不为满"这一条件发生.
}
(ir->item_buffer)[ir->write_position] = item; // 写入产品.
(ir->write_position)++; // 写入位置后移.
if (ir->write_position == kItemRepositorySize) // 写入位置若是在队列最后则重新设置为初始位置.
ir->write_position = 0;
(ir->repo_not_empty).notify_all(); // 通知消费者产品库不为空.
lock.unlock(); // 解锁.
}
int ConsumeItem(ItemRepository *ir)
{
int data;
std::unique_lock<std::mutex> lock(ir->mtx);
// item buffer is empty, just wait here.
while(ir->write_position == ir->read_position) {
std::cout << "Consumer is waiting for items...\n";
(ir->repo_not_empty).wait(lock); // 消费者等待"产品库缓冲区不为空"这一条件发生.
}
data = (ir->item_buffer)[ir->read_position]; // 读取某一产品
(ir->read_position)++; // 读取位置后移
if (ir->read_position >= kItemRepositorySize) // 读取位置若移到最后，则重新置位.
ir->read_position = 0;
(ir->repo_not_full).notify_all(); // 通知消费者产品库不为满.
lock.unlock(); // 解锁.
return data; // 返回产品.
}
void ProducerTask() // 生产者任务
{
for (int i = 1; i <= kItemsToProduce; ++i) {
// sleep(1);
std::cout << "Produce the " << i << "^th item..." << std::endl;
ProduceItem(&gItemRepository, i); // 循环生产 kItemsToProduce 个产品.
}
}
void ConsumerTask() // 消费者任务
{
static int cnt = 0;
while(1) {
sleep(1);
int item = ConsumeItem(&gItemRepository); // 消费一个产品.
std::cout << "Consume the " << item << "^th item" << std::endl;
if (++cnt == kItemsToProduce) break; // 如果产品消费个数为 kItemsToProduce, 则退出.
}
}
void InitItemRepository(ItemRepository *ir)
{
ir->write_position = 0; // 初始化产品写入位置.
ir->read_position = 0; // 初始化产品读取位置.
}
int main()
{
InitItemRepository(&gItemRepository);
std::thread producer(ProducerTask); // 创建生产者线程.
std::thread consumer(ConsumerTask); // 创建消费之线程.
producer.join();
consumer.join();
}
上述代码是单生产者和单消费者模型，多生产者多消费者模型只需要增加两个计数器用来计算当前已经生产/消费了多少个物品。
无锁循环队列
内核实现了一个无锁循环队列 kfifo
粘贴一下代码：
/**
* __kfifo_put - puts some data into the FIFO, no locking version
* @fifo: the fifo to be used.
* @buffer: the data to be added.
* @len: the length of the data to be added.
*
* This function copies at most @len bytes from the @buffer into
* the FIFO depending on the free space, and returns the number of
* bytes copied.
*
* Note that with only one concurrent reader and one concurrent
* writer, you don't need extra locking to use these functions.
*/
unsigned int __kfifo_put(struct kfifo *fifo,
unsigned char *buffer, unsigned int len)
{
unsigned int l;
//计算写入空间：队列大小 - 写入位置 + 读取位置
len = min(len, fifo->size - fifo->in + fifo->out);
/*
* Ensure that we sample the fifo->out index -before- we
* start putting bytes into the kfifo.
*
* 内存屏障（全屏障）
*/
smp_mb();
/* first put the data starting from fifo->in to buffer end */
/* 从队列写入位置 (mod 队列大小) 写入到队列结尾处 */
l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
/* then put the rest (if any) at the beginning of the buffer */
/* 从队列起始位置向后写入剩余数据 */
memcpy(fifo->buffer, buffer + l, len - l);
/*
* Ensure that we add the bytes to the kfifo -before-
* we update the fifo->in index.
*
* 内存屏障（写屏障）
*/
smp_wmb();
//单调递增写入位置
fifo->in += len;
return len;
}
/**
* __kfifo_get - gets some data from the FIFO, no locking version
* @fifo: the fifo to be used.
* @buffer: where the data must be copied.
* @len: the size of the destination buffer.
*
* This function copies at most @len bytes from the FIFO into the
* @buffer and returns the number of copied bytes.
*
* Note that with only one concurrent reader and one concurrent
* writer, you don't need extra locking to use these functions.
*/
unsigned int __kfifo_get(struct kfifo *fifo,
unsigned char *buffer, unsigned int len)
{
unsigned int l;
//计算读取空间：写入位置 - 读取位置
len = min(len, fifo->in - fifo->out);
/*
* Ensure that we sample the fifo->in index -before- we
* start removing bytes from the kfifo.
*
* 内存屏障（读屏障）
*/
smp_rmb();
/* first get the data from fifo->out until the end of the buffer */
/* 从缓存读取位置 (mod 队列大小) 读取到缓存结尾处 */
l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
/* then get the rest (if any) from the beginning of the buffer */
/* 从缓存起始位置读取剩余数据 */
memcpy(buffer + l, fifo->buffer, len - l);
/*
* Ensure that we remove the bytes from the kfifo -before-
* we update the fifo->out index.
*
* 内存屏障（全屏障）
*/
smp_mb();
//单调递增读取位置
fifo->out += len;
return len;
}
shared_ptr
shared_ptr本身不是一个线程安全的 STL，因此并发读写对应内存区域是不安全的。- 由于赋值操作涉及原内存释放、修改指针指向等多个修改操作，其过程不是原子操作，因此对
shared_ptr进行并发赋值不是线程安全的。 - 对
shared_ptr进行并发拷贝，对数据指针和控制块指针仅进行读取并复制，然后对引用计数进行递增，而引用计数增加是原子操作。因此是线程安全的。
#include<iostream>
#include<atomic>
using namespace std;
class Counter
{
public:
Counter()
{
count = 1;
}
void add()
{
count++;
}
void sub()
{
count--;
}
int get() const
{
return count;
}
private:
std::atomic<int> count;
};
template <typename T>
class Sp
{
public:
Sp(); //默认构造函数
Sp(T *ptr); //参数构造函数
Sp(const Sp &obj); //复制构造函数
~Sp(); //析构函数
Sp &operator=(const Sp &obj); //重载=
T *get(); //得到共享指针指向的类
int getcount(); //得到引用计数器
private:
T *my_ptr; //共享指针所指向的对象
Counter* counter; //引用计数器
void clear(); //清理函数
};
//默认构造函数，参数为空，构造一个引用计数器
template<typename T>
Sp<T>::Sp()
{
my_ptr = nullptr;
counter = new Counter();
counter->add();
}
//复制构造函数，新的共享指针指向旧的共享指针所指对象
template<typename T>
Sp<T>::Sp(const Sp &obj)
{
//将所指对象也变为目标所指的对象
my_ptr = obj.my_ptr;
//获取引用计数器，使得两个共享指针用一个引用计数器
counter = obj.counter;
//使这个对象的引用计数器 +1
counter->add();
};
//重载=
template<typename T>
Sp<T> &Sp<T>::operator=(const Sp&obj)
{
//清理当前所引用对象和引用计数器
clear();
//指向新的对象，并获取目标对象的引用计数器
my_ptr = obj.my_ptr;
counter = obj.counter;
//引用计数器 +1
counter->add();
//返回自己
return *this;
}
//创建一个共享指针指向目标类，构造一个新的引用计数器
template<typename T>
Sp<T>::Sp(T *ptr)
{
my_ptr = ptr;
counter = new Counter();
}
//析构函数，出作用域的时候，调用清理函数
template<typename T>
Sp<T>:: ~Sp()
{
clear();
}
//清理函数，调用时将引用计数器的值减 1，若减为 0，清理指向的对象内存区域
template<typename T>
void Sp<T>::clear()
{
//引用计数器 -1
counter->sub();
//如果引用计数器变为 0，清理对象
if(0 == counter->get())
{
if(my_ptr)
{
delete my_ptr;
}
delete counter;
}
}
//当前共享指针指向的对象，被几个共享指针所引用
template<typename T>
int Sp<T>::getcount()
{
return counter->get();
}
template<typename T>
T * sp<T>::get()
{
return my_ptr;
}
1 Like
LRU 替换算法实现
一个 leetcode 题，要求 O(1) 查找 O(1) 以 LRU 方式替换 cacheline。
使用双向链表实现即可，用 STL list 比较方便。
class LRUCache {
public:
LRUCache(int capacity) {
this->capacity=capacity;
}
int get(int key) {
auto pos=_lruHash.find(key);
if(pos!=_lruHash.end()){
//Cache 命中，调整计数器 更新 key 对应的节点的位置
list<pair<int,int>>::iterator ptr=pos->second;
//转移节点库函数 std::list::splice
//void splice (iterator position, list& x, iterator i);
//Transfers elements from x into the container, inserting them at position.
//将 x 的第 i 个节点转移带 position 位置上
_lruCacheList.splice(_lruCacheList.begin(), ptr);
return pos->second->second;
}
return -1;
}
void put(int key, int value) {
auto pos=_lruHash.find(key);
if(pos!=_lruHash.end()){
//更新 Cache，更新对应节点的位置
list<pair<int,int>>::iterator ptr=pos->second;
ptr->second=value;//更新数据
_lruCacheList.splice(_lruCacheList.begin(),ptr);
}
else{
//新增 Cache
if(capacity==_lruHash.size()){
//满了，替换删除尾上的数据
pair<int,int>&back=_lruCacheList.back();
_lruHash.erase(back.first);
_lruCacheList.pop_back();
}
_lruCacheList.push_front(make_pair(key,value));
_lruHash[key]=_lruCacheList.begin();
}
}
private:
unordered_map<int,list<pair<int,int>>::iterator>_lruHash;//方便查找
list<pair<int,int>>_lruCacheList;//保存数据
size_t capacity;
};
/\*\*
\* Your LRUCache object will be instantiated and called as such:
\* LRUCache\* obj = new LRUCache(capacity);
\* int param\_1 = obj->get(key);
\* obj->put(key,value);
\*/
页表的 LRU 替换也类似。
1 Like
-
读写内存的安全性问题
物理内存本身是不限制访问的，任何地址都可以读写，而现代操作系统需要实现不同的页面具有不同的访问权限，例如只读的数据等等 -
进程间的安全问题
各个进程之间没有独立的地址空间，一个进程由于执行错误指令或是恶意代码都可以直接修改其它进程的数据，甚至修改内核地址空间的数据，这是操作系统所不愿看到的 -
内存读写的效率问题
当多个进程同时运行，需要分配给进程的内存总和大于实际可用的物理内存时，需要将其他程序暂时拷贝到硬盘当中，然后将新的程序装入内存运行。由于大量的数据频繁装入装出，内存的使用效率会非常低。
虚拟内存
内存分段
1、内存分段
将虚拟内存分段，比如代码段、数据段、栈段、堆段等。
A、分段机制下，物理内存与虚拟内存如何映射的
分段机制里，由段选择因子和段内偏移量
段选择因子：保存在段寄存器中，里面包含有段号、标志位等。段号指向段表，段表保存段的基地址、段的界限和特权等级等。
段内偏移：一般物理地址等于段基地址 + 段内偏移。
B、存在问题：
内存碎片
内存分段是按需分配，不会产生内部碎片，但是会产生外部碎片，可能会产生多个离散的空闲内存分区不太容易复用。解决外部碎片的方法是内存交换，把虚拟内存的各段先一个个交换到外存，存到硬盘，再一个个交换过去，内存交换效率低。
如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。
内存分页
分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，我们叫页。在 Linux 下，每一页的大小为 4KB。
内存分页产生页表和虚拟页号
一般来说，物理地址是知道虚拟页号和页内偏移，然后根据虚拟页号（虚拟页号是页表的索引项），到相应的页表（页表是存储在内存中的）中查找到物理页号，物理页号 + 页内偏移等于物理地址 ——（其中主要是 MMU 内存管理单元发挥作用）
A、存在问题：
内存碎片
分页机制不是按需分配，是分配适当的页表，页表每个是固定大小 4K，所以会产生内部碎片，因为大概率会有一个页表不是完全填充的。这就是内部碎片问题。
分页机制解决内存交换效率低的问题：
分页机制，在内存交换的时候只交换几个页，在此过程中，会有换入、换出操作，就是将内存页面从内存换入或换出到磁盘。相比于分段机制将整个段进行内存与磁盘间的交换，提高了内存交换的效率。
存放页表会占用内存（空间上的缺陷）
因为操作系统是可以同时运行非常多的进程的，那这不就意味着页表会非常的庞大。
在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万（2^20）个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。多进程就需要耗费很多内存。
如何解决分页机制的占用内存的问题：
采用多级页表。由于局部性原理，对于大多数程序，其用到的空间远小于 4G，所以其对应的页表项有的是空的，所以如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表，这样占用的内存空间就是大大减少。
虚拟内存好处
第一，虚拟内存可以使得进程对运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域。
第二，由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。
第三，页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性。
第四，解决物理内存的离散式存储问题，虚拟内存中连续存储解决了物理内存碎片化资源利用率过低的问题。
内存分配
用户态调用 malloc 会分配堆的内存空间，实际上完成了一次内存映射。
内存映射对应的系统调用主要有 brk() 和 mmap()，小块内存（<128K）使用 brk 来分配内存，大块内存（>128K），使用 mmap 来分配内存。
brk
小块内存在释放的时候，不会立即释放，而是被缓存起来，可以通过 brk 来重复利用。这种方式减少了缺页中断发生的频率，提高了访存效率，但是这种方式容易造成内存碎片化。
mmap
大块内存在释放的时候直接归还系统，每次 mmap 必发生缺页中断，频繁内存分配会造成大量缺页中断，降低性能。
1 Like
我让 gpt 给我做也是这个写法
哪个啊？LRU 那个？我都上网随便看了几眼粘了一份
有没有可能，CRTP 和虚函数不是一个层面上的东西。虚函数对应的是动态派发。
我哪句话写的有问题吗？
对比 CRTP 和虚函数的优劣是 Jump 面试时候问的原题
你妹提优点
奥奥，比较的时候应该是限定了 crtp 和虚函数都可以实现的场景，不过确实可以补充一下，CRTP 不能动态派发。
两方的优点都写在对方的缺点里了，反过来看就行
C++ 支持 RTTI 的三种主要形式是什么？
（感觉这道笔试题出的太烂）
常见：typeid + dynamic_cast
似乎还有一个 std::bad_cast
内存屏障与编译器屏障（C++）
内存屏障与内存顺序
内存屏障用来阻止处理器重排内存操作，是硬件或编译器层面上的工具。
内存顺序指在多线程程序中多个线程如何观察彼此的读写操作，是 C++ 提供的高级抽象。它通过指定不同的内存顺序模型隐式地插入内存屏障。程序员不需要直接操作内存屏障，而是通过原子操作与内存顺序模型来实现对内存访问顺序的控制。
二者都是为了控制内存操作，防止指令重排、缓存一致性问题带来的意料之外的错误
内存顺序
讨论的是单线程内指令执行顺序对多线程影响的问题。不论携带怎样的内存顺序，单独的操作只会影响单个线程，但几个线程可能会经由变量的同步建立间接的顺序关系，从而被各自的内存顺序影响。
内存顺序标记
c++ 标准库定义了 6 种内存顺序，按照从宽松到严格的顺序：
memory_order_relaxed：宽松操作，仅保证原子操作自身的原子性memory_order_consume：读屏障，只影响当前 load 原子变量及依赖变量的写入，其他与memory_order_acquire一样。C++20 中弃用memory_order_acquire：读屏障，当前线程所有的读写操作不得重排至当前操作之前，使得其他线程中相同原子变量在 release 之前的写入对当前线程时可见的。即对于相关内存位置的 load 施加“acquire”占有，一定读到最新值。memory_order_release：写屏障，当前线程所有的读写操作不得重排至当前操作之后，使得当前操作的写入对于其他线程中相同原子变量在 acquire 之后是可见的。即对于相关内存位置的 store 施加“release”释放，一定写入最新值。memory_order_acq_rel：读写屏障，当前线程中的读写操作不能重排至当前操作之后也不能重排至当前操作之前memory_order_seq_cst：读写屏障，对于所有线程看见的读写操作顺序是一致的
其中
- 所有原子操作默认的内存顺序标记是
std::memory_order_seq_cst - 两种读屏障：
memory_order_consume只影响当前变量和依赖它的变量；memory_order_acquire影响当前操作前的所有变量 - 两种写屏障：
memory_order_acq_rel只对当前线程有效；memory_order_seq_cst对全局有效
协作组合
常见的几种协作组合：
-
宽松顺序：
memory_order_relaxed仅保证原子性，允许所有指令重排
-
释放 - 获得序：
memory_order_release+memory_order_acquirerelease 前的写操作一定到位，acquire 的读操作一定最新
-
释放 - 消费序：
memory_order_release+memory_order_consume比释放获得序宽松一些，仅同步了原子操作本身的原子变量及与它产生依赖关系的变量
-
序列一致顺序
memory_order_seq_cst拒绝一切重排，对所有线程可见
举个例子：
首先定义两个变量
std::atomic<std::string *> ptr;
int data;
对于释放获得序：
void producer() {
auto *p = new std::string("Hello");
data = 42;
// 编译器不能将 data = 42 这条指令移动到 store 操作之后
// memory_order_release 将修改后（写操作）的结果释放出来，其他线程使用 memory_order_acquire 可以观测到上述对内存写入的结果。此处保证 producer 的修改一定写入
ptr.store(p, std::memory_order_release);
}
void consumer() {
std::string *p2;
// memory_order_acquire 读取到最新值，其他线程使用 memory_order_release 前的值一定可以读到。此处保证 consumer 一定读取到 producer 写入的值
while (!(p2 = ptr.load(std::memory_order_acquire)))
;
// 执行到此处说明 p2 是非空的，即 data = 42 的指令已经执行了（memory_order_release 保证）
// 且此时 data 必定等于 42，p2 必定为“Hello”（memory_order_acquire 保证）
assert(*p2 == "Hello");
assert(data == 42);
// 不会出错
}
对于释放消费序：
void producer() {
std::string* p = new std::string("Hello");
data = 42;
ptr.store(p, std::memory_order_release);
}
void consumer() {
std::string* p2;
while (!(p2 = ptr.load(std::memory_order_consume)))
;
assert(*p2 == "Hello"); // 不会出错：*p2 从 ptr 携带依赖
assert(data == 42); // 有可能出错：data 不从 ptr 携带依赖
}
内存屏障
c++ 标准库中提供接口
std::atomic_thread_fence：显式的内存屏障。与内存顺序标记配合使用，将线程分为若干个阶段，每个阶段需要等待其他线程完成特定操作之后才能进入下一阶段。对于所有数据有效，不仅仅是原子变量。
使用时可以将原子变量都设置为 memory_order_relaxed，仅依靠内存屏障来实现对内存的控制
例子：
std::atomic<bool> x,y;
void write_x_then_y() {
x.store(true, std::memory_order_relaxed); // 1
std::atomic_thread_fence(std::memory_order_release); // 2.a 写屏障
y.store(true, std::memory_order_relaxed); // 2.b
}
void read_y_then_x() {
while(!y.load(std::memory_order_relaxed)); // 3.a
std::atomic_thread_fence(std::memory_order_acquire); // 3.b 读屏障
assert(!x.load(std::memory_order_relaxed));// 4
}
可以认为：
- 2.a 写屏障向下和 2.b 写操作相结合，将 2.b 提升为 release-store
- 3.b 读屏障向上和 3.a 读操作相结合，将 3.a 提升为 acquire-load
- 同步关系与前面举的内存顺序的例子相似，保证了 1 一定先于 4
内存屏障与编译器屏障
编译器屏障仅影响编译器。防止编译器重排指令，确保最终生成的汇编代码保留了源代码中指定的顺序，但不会生成实际的硬件指令，因此不会影响 CPU 或内存的访问顺序。不能处理线程并发带来的缓存一致性、内存可见性问题，常用于单核处理器。
内存屏障同时影响编译器与 CPU。不仅防止编译器重排操作，还会生成硬件指令影响 CPU 的内存访问顺序。确保线程之间的数据同步，常用于多核处理器。
编译器屏障
std::atomic_signal_fence：编译器屏障，对所有数据有效。用于防止编译器在信号处理程序或与硬件交互时重排指令。volatile关键字：- 对于某个 volatile 变量，与该变量相关的操作必须对内存进行读写，而不能仅仅读写寄存器中的缓存值。
- 对于多个 volatile 变量，它们之间的访问顺序不会被编译器改变
编译器屏障相当于告诉编译器，这些变量的值可能会在程序的控制之外发生变化，不可以假设其不变。常用于信号处理、硬件交互、嵌入式系统中断程序。
举个例子：
// thread1
volatile bool tag = true;
volatile int x = 0;
while(tag);
assert(!x);
// thread2
x = 10;
tag = false;
在单核处理器上“伪并发”这两个线程，volatile 在此处有两个作用：
- 每次都从内存中读取 tag 最新值，避免 thread1 死循环
- x 和 tag 的读写顺序和源代码中一致，即 x=10 一定发生在 tag=false 之前
但在多核处理器上“真并发”这两个线程时，即使 volatile 强制编译器从主存读取或写入，具体实现仍然由 CPU 决定。它不能控制 CPU 缓存层次结构，CPU 仍可能使用自己的缓存来处理内存访问（：简单来说就是，它以为自己读/写到主存里了，但其实没有），此时就需要使用前文所说的各种内存屏障来实现需求的逻辑了。
3 Likes