分时操作系统中的多任务编程
早期的可编程电子计算机都遵循串行单任务模型, 即单个程序运行期间无法同时执行其他任务, 所有的运算资源都被当前运行的程序所独占. 然而串行程序在运行过程中访问外部存储设备、网络以及数据库时造成的CPU运算资源大量浪费也逐渐引起了人们的重视, 以多任务思想为核心的多进程模型就在这样的背景下诞生了.
并行与并发
在实际应用中, 并发（concurrency）的出现时间要早于并行（parallel）. 作为对程序运行时资源的抽象, 进程的概念最早出现在二十世纪六十年代. 对操作系统来说, 进程是其分配内存、文件句柄、套接字等资源的基本单位, 即使这些资源是由进程内部的线程所申请的, 最终也会被分配到进程的地址空间中. 借助虚拟化技术与调度算法, 操作系统可以为每个进程模拟出独立的虚拟地址空间和运算资源, 这就是并发编程的理论基础.
Linux是典型的分时操作系统, 其特点是通过对硬件设备虚拟化将运算资源抽象为时间片, 内核通过名为完全公平调度（Completely Fair Scheduler, CFS）的动态优先级抢占式时间片分配算法来调度进程, 这种微观层面的快速多任务切换最终体现为在单个处理设备上实现宏观层面的并发多任务处理. 在现代操作系统中, 进程、线程（包括协程）、I/O复用是典型的并发手段; 而硬件层面的CPU超线程技术, 是通过添加额外控制单元实现指令层面的并发执行.
真正意义上的并行计算机直到七十年代末期才被CMU设计并制造, 并行计算理论的核心就是对任务的合理拆分以及数据同步. 大到超级计算机和分布式计算机集群, 小到显卡与多核处理器, 并行多任务能够在硬件层面真正实现同时处理, 但不容忽视的通信成本也会随着计算设备的增加而显著增长. 在多核处理器或显卡中, 可以通过多级高速缓存的方式实现处理器内部的数据共享; 而在分布式系统中, 也可以通过Redis、Memcached等高性能缓存中间件实现机器之间的数据同步. 但缓存容量毕竟有限, 如果发生缓存穿透、击穿或雪崩, 不仅处理效率会在短时间内显著降低, 整个系统也有宕机的风险.
与适用于I/O密集型的并发不同, 并行更适合处理计算密集型任务, 且加速效果与数据交换的频率成反比例关系. 而在实际应用中需要根据业务场景选择多任务方案, 例如: Nginx通过给每个核心绑定一个进程来实现并行, 然后在每个进程内部通过用户级线程（协程）实现并发.
简要总结并行与并发的区别:
- 并行（parallel） - 在多个运算设备上同时分别执行多个任务, 是硬件层面的同时执行, 难点在于对任务的分割、合并以及数据的同步. 并行编程适用于运算密集型场景, 例如: 模型训练、解方程组、图形渲染等.
- 并发（concurrency） - 在单个运算设备上同时处理多个任务, 通过软件层面的虚拟化来实现宏观时间段内的同时执行, 难点在于上下文切换成本以及高并发场景下的状态维护. 并发编程适用于I/O密集型场景, 例如: 网络服务器、数据库服务器、分布式爬虫等.
同步阻塞与异步非阻塞
处于就绪态的进程在分配到时间片之后会进入运行态, 但如果在运行过程中调用了wait()、网络I/O、文件I/O等默认阻塞的系统调用则会进入阻塞态. 阻塞（blocking）的特点是不占用时间片, 直到内核处理完所等待的事件之后才会通知进程解除阻塞并再次进入就绪态. 而非阻塞（non-blocking）系统调用的特点是会立即返回当前状态, 即使当前内核没有准备好请求的I/O数据, 进程也会在时间片用尽之前一直处于运行态. 下面是一段通过阻塞socket发送HTTP网络请求的核心代码:
1
如果在构造socket对象时不显式指定
默认的socket
以queue模块中的队列为例, put()和get()是阻塞方法, 调用之后如果不满足条件则会一直阻塞; put_nowait()和get_nowait()是非阻塞方法, 调用之后会立刻返回结果, 如果不满条件则会抛出异常.
在non_blk线程中调用了非阻塞API, 因此循环体可以不停地执行; 在blocking线程中调用了阻塞API, 因此线程暂时进入阻塞态, 直到条件满足之后解释器才通知循环体继续执行.
如果在进程初始化或运行时出现内存不足的现象, 操作系统可能会将部分进程映射到外部存储设备上, 这些进程的状态会变为就绪挂起或阻塞挂起. 由此可以看出, 是否进入阻塞或非阻塞状态取决于程序所调用的API, 而挂起操作是由操作系统所发起的.
用户级线程与内核级线程
进程的广泛使用显著提升了CPU利用率, 然而每个进程拥有独立虚拟地址空间的特点却导致其创建、维护和通信成本过高, 因此并不适用于高并发场景.
- 创建成本: 在早期版本的系统中,
fork()会完全拷贝父进程的数据段、堆、栈给子进程并共享代码段, 如果子进程需要调用exec()覆盖地址空间, 那么这次拷贝就是无意义的. 现代操作系统中引入了写时拷贝技术(Copy-On-Write, COW)来解决这个问题, 然而内核还是需要给子进程分配文件描述符并创建虚拟地址空间. 尽管使用进程池（Process Pool）可以显著降低进程反复创建与销毁时造成的资源浪费, 但进程状态维护的成本仍然不容小觑. -
维护成本: 为了描述与控制进程的运行过程, 内核需要为每个进程维护进程控制块（Process Control Block, PCB）. 在Linux中使用
task_struct结构体存放进程的状态、标识符、调度信息、程序计数器、内存指针、寄存器上下文、I/O状态、处理器时间以及其他必要信息, 如此复杂的结构导致进程在切换地址空间以及硬件上下文时会占用大量CPU资源, 而且切换后缓存命中率的降低也会进一步影响处理效率. - 通信成本: 进程地址空间的独立导致除共享内存之外的进程间数据交互都需要通过内核中转, 这显著提升了进程间通信（InterProcess Communication, IPC）的成本. 其中管道（PIPE）和命名管道（FIFO）因为只能传递无结构数据且速度较慢而作用有限; 信号量（Semaphore）一般只被用于状态同步; 软中断信号（Signal）所能承载的信息太少因此很少使用; 而在分布式系统中则只能使用具有跨机器通信特点的套接字（Socket）和消息队列（MQ）.
上述问题在线程（thread）的概念被引入之后才得以有效緩解. 在现代操作系统中, 线程是进程中实际操作的执行者, 每个进程至少包含一个主线程, 这意味着操作系统给进程分配的时间片最终会被线程所使用, 因此可以说进程是CPU资源分配的最小单位. 相比于进程来说, 线程的创建成本更低、运行时需要维护的状态更少, 此外, 属于相同进程的多个线程之间可以共享该进程地址空间内的数据, 这显著降低了切换和通信的成本.
用户级线程（User-Level Thread）的出现时间要早于内核级线程（Kernel-Level Thread）. 线程的概念在诞生之后的很长一段时间内都没有被操作系统所支持, 因此早期的程序需要在进程的用户态自行实现对线程的创建、维护与切换等工作, 这就是所谓的用户级线程（协程）. 早期的Liunx通过clone()系统调用将轻量级进程（LWP）通过与父进程内存共享的方式模拟为内核级线程, 但由于效率过低且不符合POSIX threads（pthread）标准, 这种实现方式在2.6版本之后被Native POSIX Thread Library（NPTL）所取代, 通过getconf GNU_LIBPTHREAD_VERSION命令可以查看当前系统所用的内核级线程库.
-
用户级线程的优缺点: 优势在于线程的调度完全在用户态进行, 线程切换时不需要频繁在用户态和内核态之间拷贝数据, 因此时间片的利用效率在高I/O并发的场景下会显著提升. 但缺点在于无法有效利用多核心运算资源来处理计算密集型任务, 因为无论多少个用户级线程对内核来说都是透明的, 这导致同一个进程内的所有用户级线程只能利用本该属于主线程的时间片.
-
内核级线程的优缺点: 优势在于调度被操作系统所控制, 因此内核会根据线程的数量分配运算资源, 这让内核级线程能够有效执行计算密集型任务. 但内核级线程在切换时需要在用户态与内核态之间拷贝数据, 尽管这种代价远小于对进程的切换, 但再高并发场景下仍然是不可忽视的.
同步原语与GIL
线程锁 乐观锁 悲观锁 死锁的 判断,避免,处理方式
GIL 还意味着虽然 CPython 可以是多线程的，但在任何给定的时间里只能执行 1 个线程
出于对字节码执行时安全性的考虑, 通过C语言编写的Python解释器会通过全局解释器锁（Global Interpreter Lock, GIL）来管理每个进程实例所创建的线程. GIL模拟了单核CPU对多线程的调度, 只有获得GIL的线程才会被执行, 并且在执行一段时间或遇到阻塞I/O之后所持有的GIL就会被释放, 这样循环下去就能够在主线程里模拟出多线程并发的效果. GIL的存在导致通过内置的threading模块创建的线程都是抢占式用户级线程, 线程切换时GIL频繁的释放与竞争让本就不适合处理计算密集型任务的用户级线程在面对I/O密集型任务时也显得力不从心, 因此在大部分情况下Python中多线程的处理效率反而低于单线程.
可以说用户级线程的缺点被GIL无限放大, 而其维护和切换成本低的优点也被复杂的锁机制所抵消, 这显著体现了内核级线程在实际应用中的局限性. 一种解决方法是像Numpy一样利用C-Python接口直接绕开GIL, 在C语言层面直接调用内核级多线程; 另一种方案是更换解释器, 基于JVM的Jython和基于.Net的IronPython都没有GIL锁, 但版本落后于主分支且更新不稳定导致其应用场景受限. 因此目前高I/O并发场景下的最佳解决方案是在单线程中使用非抢占式用户级线程以异步非阻塞的方式切换控制流, 也就是协程（Coroutine）.
协程与I/O多路复用
协程（Coroutine）是非抢占式用户级线程的一种具体实现, 其特点是通过用户态上下文切换实现对单线程计算资源的进一步细分, 因此也被称为微线程.
在进程地址空间中,
根据协程切换时对上下文的处理方式不同, 可以分为有栈协程和无栈协程.
栈的作用实在函数执行完毕后弹出最顶层, 从而恢复现场
有栈协程拥有自己独立的函数调用栈,
无栈协程在堆中维护自己的状态, 只需要将栈帧压入栈即可, 但限制在于执行完毕后必须返回原有的调用者 因此无栈协程一般具有传染性
def A(): async def B(): await xxxxx await B()
MAIN A B
MAIN C D
MAIN A B C D
对等协程（Symmetric）
和主从协程
注意: Go语言中的goroutine比较特殊, 它的协程可能运行在一个或多个线程上。当某个线程阻塞，GO 会自动将新的协程分配到其他线程中
在Python早期版本中是以生成器函数的方式实现上下文切换, 生成器函数的特点就是通过yield可以实现对当前函数的装
在3.4版本中添加了基于事件循环处理异步任务的asyncio, 到了3.5版本又通过async/await关键字用于简化了协程的调用逻辑, 并且
同时也是对分配给线程的 协程的是
就是可以在单线程中实现函数执行顺序的主动切换, 首先以greenlet为例,
通过内置的生成器关键字也可以实现协程, yield用于保护状态, 通过yield from可以实现线程运行权的切换, 但线程的控制权仍然然被
Python中协程的特点是可以在提交异步任务的同时主动交出控制权, 从而让其他任务充分利用当前线程的计算资源, 因此非常适合处理网络请求、文件和数据库读写.
计算资源的分配以及对回调等异步策略的管理. 主动转让控制权, 由事件循环控制回调
根据APUE的定义, 异步I/O就是非阻塞, 同步I/O就是阻塞, 非阻塞
对协程来说重要的是设计事件循环, 其次是对任务的上下文进行合理描述与读写.
https://zhuanlan.zhihu.com/p/40279108
通过yield保存上下文信息, 通过send重新加载
实现真正的.
异步处理模块asyncio当作真正的来使用.
协程（Coroutine）是用户级线程的一种实现方式,
想要在单线程中实现
必须在程序内部
每个以asyncio.run()方式运行的线程会被自动添加用于执行异步任务、
并维护每个任务的状态, 当有异步任务通过await主动让出控制权时, loop会挑选一个可执行的异步任务接管控制权,
尽管threading和asyncio都适用于对网络、文件、数据库等阻塞I/O的处理, 但更低的切换成本让asyncio能够处理并发数量更高的场景.
根据APUE中的定义,
多路I/O复用模型
时间复杂度
select poll epoll kqueue