System|并发|进程线程协程综述

在操作系统中，我们可以选择进程、线程、协程作为我们的基本并发单元。那么，具体来说，每种选型都有什么特点呢？以下是对他们全面的综述。

目录

• 进程: 地址隔离、虚拟化地址隔离、资源隔离、权限隔离、IPC
• 线程: 调度、同步原语、可见性、有序性、线程本地存储、并发模型
• 协程: 有栈协程、共享栈协程、无栈协程

进程

进程的核心在于隔离，而为了隔离之中进行通信，又引入开销巨大的IPC。因为隔离的存在，如果我们希望运行多种类型的服务，或者虚拟化，或者不需要通信时，选型多进程。

地址空间隔离

在OS中，地址空间隔离通过页表实现。CR3或者TTBR寄存器指向根页表。总体来说，地址空间的寻址逻辑如下:

• Cache->TLB->CR3->L0->L1->L2->L3->Page
• Cache->TLB->CR3->L0->L1->L2->Big Page
• Cache->TLB->CR3->L0->L1->Huge Page

• ASID声明TLB所属进程避免TLB flush缓存失效，global TLB作为内核地址空间共享
• 引入多级页表的目的，制造"空洞"，减少内存开销
• 引入大页的目的，减少TLB，减少寻址页表级数；缺陷资源浪费，提高复杂度。
• mmap, 只进行映射不进行内存分配，通过page fault惰性分配
• 换页或内存压缩，内存不足时将物理内存复制在磁盘上或者压缩
• COW，fork时标记write保护，写时page fault复制，引用计数为1则不复制
• 内存去重，反向COW，将内容相同的物理页合并为COW页
• 绑核，避免进程在其他核上运行，缓存失效。

有趣的是，big table的tablet寻址操作和页表很像。

Client Cache->Chubby->Root->MetaData->Data

虚拟化地址空间隔离

对于虚拟化环境，则需要进行两阶段翻译，GVA->GPA->HPA

需要24次寻址操作，因此缓存和TLB非常重要！使用VMID声明所属VM避免TLB刷新

一阶段页表page fault由VM处理，二阶段则由VMM处理

资源隔离

著名的Docker就是基于Linux提供的Cgroup实现的，限制CPU、IO、内存等资源。

权限隔离

一方面，进程具有自己的CPU特权级，因此不同进程所能执行的指令和访问的地址不同。

另一方面，进程拥有自己的capability(file descriptor)，决定能访问的内核对象及权限。事实上，地址空间本身就是一种capability

IPC

进程通过独占地址空间实现了隔离，然而，某些时候，我们希望进程之间协作。

• 模块化: 数据库单独在一个进程中，可以被复用
• 加速计算: 不同进程专注于特定的计算任务，性能更好
• 信息共享: 直接共享已经计算好的数据，避免重复计算

两个(或多个)不同的进程，通过内核或其他共享资源进行通信，来传递控制信息或数据。

确切来说，包含进程间同步和进程间通信

线程

进程的开销是重量级的。

从时间角度:

• 进程之间存在页表隔离，必须通过IPC通信，经过内核态。
• 进程切换后缓存失效，访存速度严重下降
• 切换上下文的操作复杂，需要改变的寄存器多

从空间角度:

• 每个进程都需要独立的地址空间，无法复用代码、数据段。
• 进程的PCB存在和权限有关的数据，冗余。

线程的核心在于共享，地址空间彼此互相可见，因此不需要繁重的IPC开销。线程之间的竞争成为难题。

调度

CFS算法，红黑树存储所有线程，每次取vruntime最小的线程执行并且增加虚拟步长。如果新增线程，其vruntime为红黑树中最小的vruntime防止饥饿。步长和权重成反比。

同步原语

为了防止Race Condition，我们需要利用同步原语保护临界区。同步原语的底层是操作系统提供的两个硬件原子性操作CAS和FAA。

可见性

为了确保多核之间的可见性，我们需要使得对象分配在内存上而非寄存器上，从而经由缓存一致性协议。通过在对象前增加volatile保证。

有序性

由于CPU乱序执行，多核情况下可能发生意外使得临界区没有被保护。此时我们需要手动加入内存屏障。在java中volatile可以同时保证可见性和有序性，而C/C++则通过系统宏。

• Arm基于弱序一致性模型，不保证任何对不同的地址的读写操作顺序
• Intel基于TSO一致性模型，不保证对不同的地址的写-读的顺序

线程本地存储

通过在全局变量前增加_thread实现，tpidr或者fs寄存器作为基地址寻址。

在JVM通过Thread Local Map，基于线性探查的哈希表存储，每次hash+=0x61c88647。

并发模型

基于线程池

基于Reactor的事件驱动模型

基于Reactor的分阶段事件驱动模型

协程

从时间角度:

• 线程的上下文切换必须先进入内核态并切换上下文, 这就造成了严重的调度开销
• 内核态和用户态存在页表隔离，用于防止meltdown攻击，在ARM中通过ttbr实现
• 线程的调度算法是通用的，对于内核而言，它会以公平的方式(CFS)进行调度，而某些时候如果我们利用用户态的信息自主调度能够做出更好的决策。
• 线程的结构体存在于内核中，在pthread_create时需要进入内核态，频繁创建开销大

从空间角度:

• 线程的栈空间通常在MB级别，而服务器往往只是无状态地转发，并不需要这么大的栈空间
• 线程利用TCB存储上下文和调度状态，可能存在冗余的信息

有栈协程

通过修改RA完成执行流的切换，协程的栈位于堆上，手动保存或取出寄存器。

共享栈协程

为了节约内存引入共享栈机制，用拷贝共享栈的时间换取每个协程栈的空间，共享栈的内存通常较大，视作许多协程栈的堆叠，每个协程栈无需占据128K而是根据size动态分配。

如果即将执行的协程并不是共享栈的持有者，则让共享栈的持有者将自己的栈(在共享栈顶)存入buffer中，然后将共享栈转移给即将执行的协程。

在协程切换完成后，即将执行的协程将自己的栈从buffer中取出并复制到共享栈中。

void co_swap(stCoRoutine_t* curr, stCoRoutine_t* pending_co)
{
 	stCoRoutineEnv_t* env = co_get_curr_thread_env();

	//get curr stack sp
	char c;
	curr->stack_sp= &c;

	if (!pending_co->cIsShareStack)
	{
		env->pending_co = NULL;
		env->occupy_co = NULL;
	}
	else 
	{
		env->pending_co = pending_co;
		//get last occupy co on the same stack mem
		stCoRoutine_t* occupy_co = pending_co->stack_mem->occupy_co;
		//set pending co to occupy thest stack mem;
		pending_co->stack_mem->occupy_co = pending_co;

		env->occupy_co = occupy_co;
		if (occupy_co && occupy_co != pending_co)
		{
			save_stack_buffer(occupy_co);
		}
	}

	//swap context
	coctx_swap(&(curr->ctx),&(pending_co->ctx) );

	//stack buffer may be overwrite, so get again;
	stCoRoutineEnv_t* curr_env = co_get_curr_thread_env();
	stCoRoutine_t* update_occupy_co =  curr_env->occupy_co;
	stCoRoutine_t* update_pending_co = curr_env->pending_co;
	
	if (update_occupy_co && update_pending_co && update_occupy_co != update_pending_co)
	{
		//resume stack buffer
		if (update_pending_co->save_buffer && update_pending_co->save_size > 0)
		{
			memcpy(update_pending_co->stack_sp, update_pending_co->save_buffer, update_pending_co->save_size);
		}
	}
}

无栈协程

无栈协程的特点在于所有的协程都运行在系统栈上，需要手动在堆中保存、恢复协程的所有数据（因为没有栈供存储)。

https://en.cppreference.com/w/cpp/language/coroutines： A coroutine is a function that can suspend execution to be resumed later. Coroutines are stackless: they suspend execution by returning to the caller and the data that is required to resume execution is stored separately from the stack. This allows for sequential code that executes asynchronously (e.g. to handle non-blocking I/O without explicit callbacks), and also supports algorithms on lazy-computed infinite sequences and other uses.

引用

• libco
• Java SDK
• Linux Kernel
• SEDA
• SJTU IPADS, OS/CSE
• https://en.cppreference.com/w/cpp/language/coroutines