协程与线程辨析

• 协程与线程的区别：

  • 协程只在用户态进行切换，协程上下文切换开销比较小（仅寄存器和栈），协程栈大小灵活且通常来说比较小，一个线程有多个协程，同一时间内一个线程仅执行一个协程，协程在C++通过主动让出来调度
  • 线程切换需要进入内核态，调度由操作系统控制，如果同CPU切换了属于不同进程的线程会导致上下文切换开销大（如PCB/VMA/CR3等），线程栈固定且通常大很多，线程是CPU调度的最小单元，CPU同一个时间内只执行一个线程（创建线程数的上限和虚拟内存空间有关！！！）

• 协程的栈比线程的栈小

  • 好处：在有限内存内能够创建更多协程，支持更多的并发
  • 坏处：运行在协程上的程序，函数调用不能太深，不然会爆栈

• 如何解决爆栈问题

  • 有栈协程可以手动设置栈的大小，或者部分语言可以设置动态扩容的栈
  • 无栈协程通过将协程内语句抽象为有限状态机，将各个状态离散地存在堆上来避免爆栈，不过这就比较费时间

• 协程通常用在I/O密集型的任务，比如DART一个设计就是，scan操作会同时对多个slot发出获取该slot指向的远端数据节点的RDMA read请求，当一个进程给某一个slot发出请求的时候，如果没有协程会直接阻塞等IO；有了协程之后就可以在等IO前直接让出线程的控制权，给下一个协程去根据slot发RDMA请求，维护一个等待中的协程队列，如果协程用尽或者当前层的scan没有需要再发请求的slot，那么就将等待队列中的协程唤醒，到那个时候IO应该数据也到位了

• C++中如何创建线程并且安全退出？

  • create、 join 避免使用 detach，因为detach无法被主线程回收，会导致僵尸进程等问题，空耗内存

线程和进程辨析

线程安全

线程安全主要是指对访问共享资源时候如何保证程序按照期望目标进行执行，不出现数据竞争以及未定义行为

• 互斥锁、读写锁 std::mutex
• 原子操作std::atomic，硬件指令，通常能够用在最多8字节的数据类型
• 读写锁 std::shared_mutex，允许多读单写
• 条件变量
• 信号量
• 无锁数据结构，如CAS
• 线程局部存储TLS 如thread_local，一个线程一份变量数据

RAII：资源获取即初始化

• 原理：使用局部对象（存在栈的对象）来管理资源的技术，可以认为是一种对资源申请和释放的利用栈内对象自动创建销毁的特性进行的封装，比如智能指针、lock_guard管理互斥锁、网络套接字（？）等
• std::lock_guard std::unique_lock 对象创建在栈上，存一个mutex的引用，创建的时候加锁，析构的时候解锁；当然也可以设置std::defer参数来进行创建时先暂时不加锁的设置
• std::unique_ptr std::shared_ptr也是通过类似方式，自己的指针创建在栈上，在构造函数内将传入的指针赋给内部成员指针，析构的时候根据情况释放指针所指向的资源

std::mutex

• 互斥、非递归即不可重入（尝试重复锁定会直接死锁，比如最近的操作系统内核管理Lab2，在写PF函数处理逻辑的时候由于内存管理不善，在触发了PF的时候直接调用了内核里的处理PF函数，直接重复进入锁，很麻烦，需要print查看调用栈）
• 无拷贝构造函数和移动构造函数（在C++定义中直接delete了这两个构造函数）
• try_lock其实是超时锁，超过一定时间放弃拿锁
• 无竞争情况，mutex倾向于用轻量级原子操作test-and-set compare-and-swap快速加锁或者解锁；有竞争情况会进入内核态，阻塞所有线程，维护等待队列，锁释放的时候唤醒队列内下一个线程（如当前已经被占用的时候就会让进程阻塞并且加入等待队列）

std::condition_variable

• 依赖于mutex实现并发控制，不可复制或者移动
• 陷入等待状态的线程需要被唤醒才能继续执行，且陷入等待状态的线程会释放传入的锁
• 可以设置唤醒条件，wait(unique_lock &lock, Predicate pred)，如果被虚假唤醒了（条件未满足就被唤醒），那么会内置循环，在条件满足的时候才会退出循环，否则继续等；唤醒之后会竞争锁
• notify_one()/notify_all() 唤醒队列中的一个/全部线程

std::semaphore

• 最大计数表示允许多少线程同时访问资源，对于信号量的加减并无严格顺序/同线程的要求
• acquire() 计数-1，计数为0则阻塞 release相反
• try_acquire try_acquire_until 超时尝试获取
• 不依赖mutex，本身无需额外的锁对象
• 直接用原子操作实现，底层可能是sem_t futex等

  下表来自Grok

线程池

线程池是限定一定数量线程的任务处理队列封装

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

class ThreadPool {
public:
	ThreadPool(size_t threads) : stop(false) {
		for (size_t i = 0; i < threads; i++) {
			workers.emplace_back([this]{
				for (;;) {
					std::function<void()> task; // 函数包装器，封装特定返回/参数类型的函数
					{
						std::unique_lock<std::mutex> lock(this->queue_mutex);
						this->condition.wait(lock, [this] {
							return this->stop || !this->tasks.empty();
						});
						if (this->stop && this->tasks.empty())
							return;
						task = std::move(this->tasks.front());
						this->tasks.pop();
					}
					task();
				}
			});
		}
	}
}

std::function<T>

• 性能开销：构造和赋值涉及堆分配，如果有捕获了大量变量的lambda被包装，可能导致额外的内存使用
• 该类型本身线程不安全，可能被多个线程同时访问或者修改
• 函数指针的性能比它好，可能因为函数指针就是一个地址，让PC跳转即可
• 性能开销的来源：类型擦除，因为该接口需要能够适应多种可调用类型，如普通函数、lambda函数、仿函数等，所以其自身的实现是有一个基类，具体定制可调用类型的实现由继承类实现，就一定程度涉及到内存拷贝、虚函数表间接调用等
• 性能开销的优化：SBO（小对象优化），简要来说，该对象对于std::function实现了一个栈上的缓冲区，如果要接受的数据量不是很大那就直接存在缓冲区里即可；如果一个捕获了很多变量的lambda函数，缓冲区不够那就只能在堆上分配空间

顺便回顾一下虚函数

1
2

Base* ptr = new Derived();
ptr->speak();

当基类有虚函数的时候，就会有一个该虚函数的表；当该类的指针或者引用调用虚函数的时候，程序会去查阅虚函数表找到实际调用类的函数，从而正确调用函数

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

template<class F, class... Args>
auto enqueue(F&& f, Args&&... args) // left and right value
	-> std::future<typename std::result_of<F(Args...)>::type> {
	using return_type = typename std::result_of<F(Args...)>::type; // 推导调用函数F并且传入参数Args后的返回类型，比如`int foo(double)`，那么`result_of<F(Args...)>::type`就是`int`

	auto task = std::make_shared<std::packaged_task<return_type()>>(
		std::bind(std::forward<F>(f), std::forward<Args>(args)...)
	); // bind the call of f and args... to a non-param function object，将对于函数f且传入args...参数的函数调用绑定为无参数的函数对象

	std::future<return_type> res = task->get_future(); // 用于后续获取任务执行的结果
	{
		std::unique_lock<std::mutex> lock(queue_mutex);
		if (stop) {
			throw std::runtime_error("..");
		}
		tasks.emplace([task](){(*task)();}); // 捕获shared_ptr的副本，解引用之后调用它，用lambda封装之后就满足了上面构造函数的对于std::function类型的要求
	}

	condition.notify_one();
	return res;
}

std::forward完美转发，用于保持参数的左值和右值属性
std::packaged_task本身不可以拷贝，但是需要将其存入lambda中，所以用shared_ptr管理共享任务对象；其作用是将任务与future绑定，实现异步获取结果

有关stop的读写还是加锁保护为好，毕竟可能出现update after check问题

1
2
3
4
5
6
7
8
9
10

~ThreadPool() {
	{
		std::unique_lock<std::mutex> lock(queue_mutex);
		this->stop = true;
	}
	condition.notify_all();
	for (std::thread &worker: workers) {
		worker.join();
	}
}

std::atomic内存顺序一致性

1
2
3
4
5
6
7
8
9
10

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

// 生产者线程
data = 42;
ready.store(true, std::memory_order_release); // 保证之前的写操作先完成

// 消费者线程
while (!ready.load(std::memory_order_acquire)); // 保证之后的读操作在之后
std::cout << data; // 一定能看到 data=42

具体来说，编译器会阻止release之前的任何读写操作被重排到release之后，而acquire之后的任何操作会被重排到acquire之前；对CPU来说，release相当于一个写屏障，其之前的写操作必须也对其他线程可见；同时acquire相当于读屏障，确保之后的读操作在acquire之后，那么后续的读操作就可以看到release及以前的写操作了

与memory_order_seq_cst的区别：严格顺序一致性保证每个线程看到的所有原子指令的操作顺序（这里特指结果）完全一模一样，且在线程内部，在原子操作前的操作必须早于原子操作执行，反之亦然

relaxed只保证原子性，意味着他不会约束原子操作之间的顺序，也不会约束原子操作附近的非原子操作的顺序

weak_ptr和shared_ptr辨析

• shared_ptr计数为0的时候，对象立即销毁，但是控制块不立即销毁，控制块等到weak_ptr也全部销毁之后销毁
• weak_ptr失效的表现：expired() -> true或者lock()返回空的shared_ptr

STL

• std::vector 是一个有size capacity指针的数组，会动态扩容
• std::unordered_map/set 是散列表，一般散列表的指针列表大小为素数而且大约为2倍增长的比例
• std::map/set 是红黑树
• std::deque 是分段连续的动态数组，每一段地址连续，用一个数组存指针
• std::list 是双向链表
• std::queue std::stack 的底层是基于std::deque的，他们是容器适配器
• std::priority_queue 底层基于std::vector，用堆数据结构组织元素

迭代器失效

STL 容器迭代器失效总结(超级详细)_begin()什么时候失效-CSDN博客

补充

• std::deque在索引数组重排的时候，由于其迭代器不仅仅包含了指向内存块对应元素的指针，而且还需要能够支持在不同的内存块中游走（需要存储索引数组以及当前位于哪一个内存块的下标），所以当索引数组重排的时候，begin()和end()都会失效
• std::unordered_map/set在rehash的时候会迭代器失效，而其他场景下除了被删除元素的迭代器会失效以外其余的都太会失效，类似于std::list
• std::map/set的迭代器失效只会发生在删除元素后对应元素迭代器失效，其余的由于他是链表为主的结构所以一般不会怎么样