Go并发编程 - (一)并发编程基础

并发编程基础

所谓并发编程是指在一台处理器上“同时”处理多个任务。并发是在同一实体上的多个事件。多个事件在同一时间间隔发生。

串行程序与并发程序

串行程序特指只能被顺序执行的指令列表,并发程序则是可以被并发执行的两个及以上的串行程序的综合体。并发程序允许其中的串行程序运行在一个或个可共享的CPU上,同时也允许每个串行程序都运行在专门为它服务的CPU上。前一种方式也被成为多元程序,由操作系统支持并提供多个串行程序复用多个CPU的方法。多元处理是指计算机中多个CPU公用一个存储器(即内存),并在同一时刻可能会有数个串行程序分别运行在不同的CPU之上。

并发与并行

并发和并行都可以是很多个线程，就看这些线程能不能同时被（多个）cpu执行，如果可以就说明是并行，而并发是多个线程被（一个）cpu 轮流切换着执行

进程

定义

进程是Unix及其衍生操作系统的根本。通常,我们把一个程序的执行称为一个进程,反过来讲,进程用于描述程序的执行过程。

创建

进程使用fork可以创建若干个新的进程。每个进程都有一个父进程(内核启动进程除外),都源自于父进程的一个副本,会获得父进程的数据段、堆、和栈的副本,并与父进程共享代码段。子进程调用exec可执行一个新的程序。Linux采用写时复制(copy on write)等技术来提供进程创建的效率。

由内核启动进程作为根,所有进程共同组成进程树。若一个进程优先于子进程结束。那么这些子进程将会成为内核启动进程的直接子进程。

状态

在linux系统中,每个进程在每个时刻都是有状态的

可运行状态
可中断的睡眠状态
1. 如: 等待网络连接的进程的状态,当事件发生时,对应等待队列中的一个或多个进程就会被唤醒
不可中断的睡眠状态
1. 此状态的进程不会对任何信息作出相应。准确的说,发送给此状态的进程的信号直到此状态转出时才会被传递出去,如: 等待同步的 I/O操作(磁盘I/O)完成
暂停状态或跟踪状态
1. 调试程序
僵尸状态
1. 进程即将结束,默认进入此状态,资源大部分被回收,父进程可能需要部分信息,此时进程主体已被删除只留下一个空壳
退出状态
1. 父进程忽略调结束信号,不需要保留子进程的信息，则,子进程进入此状态,进程直接结束,资源立即回收

进程的空间

用户进程总会生存在用户空间中,不能与其所在计算机的硬件进行交互。内核可以与硬件交互,但他生存在内核空间中。用户进程无法直接访问内核空间。用户空间和内核空间都是操作系统在内存中划出的一个范围,他们共同瓜分了操作系统能够支配的内存区域

操作系统

操作系统是负责整个系统最基本功能和系统管理，包括内核、设备驱动程序、启动引导程序、命令行shell或其它种类的用户界面、基本的文件管理工具和系统工具。

用户界面是操作系统的外在表象，内核是操作系统的内在核心。

内核

内核由一系列程序组成，包括负责响应中断的中断服务程序、负责管理多个进程从而分享处理器时间的调度程序、负责管理地址空间的内存管理程序、网络、进程间通信的系统服务程序等。

内核负责管理系统的硬件设备。

内核空间 - 用户空间

内核空间表示内核拥有的内存空间，用户空间表示用户程序执行时的内存空间。

内核拥有直接访问硬件设备的所有权限，用户程序不能直接访问硬件设备，因此用户程序通过系统调用和内核通信来运行。

内存区域中每一个单元都是有地址的,这些地址是通过指针来定位。指针是一个正整数,由若干个二进制位表示,二进制位的数量由计算机(CPU)的字节决定。因此,在32位计算机中有效标识位是2^32,64位中是2^64个内存单元

这儿的地址表示的虚拟地址,而不是实际的物理内存中的地址。虚拟地址标识的内存区域又称为虚拟地址空间，或称为虚拟内存。常数 TASK_SIZE将空间分为内核空间和用户空间,这个常数的值由所在计算机的体系结构决定。同时,虚拟内存的最大容量与实际可用的物理内存大小无关。内核和CPU会负责维护虚拟内存与物理内存之间的映射关系。

内核会位每个用户进程分配虚拟内存,而不是物理内存。每个用户进程分配到的虚拟内存总是在用户空间中。各个用户空间几乎是相对独立的,互不干扰

内核会把进程的虚拟内存划分位若干页,而物理内存单元的划分由CPU负责。一个物理内存单元被称一个页框。不同进程的大多数页都会与不同的页框相对应

同时同一个页框中(物理内存)可能会包含不同的页,也就是说,多个进程共享一个内存区(一种IPC方法的基础),同时,一个进程中的页,可以不对应某一个页框。可能是该页没有数据或数据还不需要使用,也可能是该页已经被移出至磁盘(是Linux文件系统的swap分区)

系统调用

用户进程无法直接操作计算机硬件,内核空间中的内核可以。所以，为了让用户空间能够操作系统底层的功能，内核会暴露出一些接口供用户进程使用。这些接口是用户空间和内核空间的唯一桥梁。

内核态和用户态

为了保证操作系统的稳定和安全，内核依据由CPU提供的、可以让进程驻留的特权级别建立了两个特权状态。内核态和用户态。大部分时间内，CPU都是处理用户态。这时CPU只能和用户空间做交互。当用户进程发出一个系统调用时，内核会把CPU从用户态切换到内核态，而后让CPU执行相应的内核函数。CPU在内核状态下是有权限访问内核的，这就相当于用户进程可以通过系统调用使用内核提供的功能。当内核函数执行完成过后，内核会把CPU从内核态切换回用户态，并将执行结果返回给用户进程。

进程的切换和调度

与其他分时操作系统一样，Linux操作系统也可拼接CPU的威力快速地在多个进程之间切换，这也称为进程间的上下文切换。如此会产生多个进程同时运行的假象。而每个进程都会认为自己独占了CPU，这就是多任务操作系统这个称谓的由来。不过，无论切换速度如何，在统一时刻正在运行的进程仅会由一个。

切换CPU正在运行的进程是需要付出代价的，切换的时候必须保存当前进程的状态，并且，如果不是第一次执行，还需要恢复此进程到上次结束的时候。除了进程的切换，内核还需要考虑下次切换时执行哪一个进程、何时切换、被换下的进程何时再换上、等等。解决类似问题的方案和任务系统称谓进程调度。

进程切换和调度是多个程序并发执行的基础。

同步

只要多个进程同时对一个资源进行访问，就很可能互相干扰，这种干扰通常称为竞态条件。

造成竞态条件的根本原因在于进程在进行某些操作的时候被中断了。虽然进程再次进行时其状态会恢复，但是外界环境可能已经在极端的时间内改变了。

执行过程中不能中断的操作称为原子操作。而只能被串行化访问或执行的某个资源或某段代码称为临界区。原子操作和临界区看起来比较类似。但是，原子操作是不能中断的，而临界区对是否可以被或走过那段却没有强制的规定，只要保证一个访问者在临界区中时，其他访问者不会被放进来就可以来。

原子操作必须由一个单一的汇编指令表示，并且需要得到芯片级别的支持，当今的CPU都提供了对原子操作的支持。这使得原子操作能够做到绝对的并发安全，并且比其他同步机制要快很多。但是，为了避免一个原子操作执行总是无法结束，而又无法中断它，内核只提供针对二进制位和整数的原子操作的原因。

相比原子操作，让串行化执行的若干代码形成临界区的这种方法更加通用。保证只有一个进程或线程在临界区之类，官方称谓互斥(mutual exclusion 简称 mutex)。实现互斥的方法必须保证排他原则(exclusion principle)，并且这种保证不能依赖于任何计算机硬件，包括CPU。Go的sync代码包中包含了对互斥的支持。

信号

操作系统信号(signal)是IPC中唯一一种异步的通信方法。它的本质是用软件来模拟硬件的中断机制。信号用来通知某个进程有某个事件发生了。

IPC(Inter-Process Communication)进程间通信,Linux定义了六种方式

(1) 半双工Unix管道
(2) FIFOs(命名管道)
(3) 消息队列
(4) 信号量
(5) 共享内存
(6) 网络Socket

Linux 系统中使用 kill -l 可以看到62个信号(没有32和33的信号)，其中，编号从1到31的信号属于标准信号(也称为不可靠信息)，而编号从34到64的信号属于实时信号(也称为可靠信号)。对于同一个进程来说，每种标准信号只会被记录并处理一次。并且如果发送给某一个进程的标准信号的种类有多个，那么它们处理顺序也是完全不确定的。而实时信号解决了标准信号的这两个问题。即多个同种类的实时信号都可以记录，并且它们可以按照信号的发送顺序被处理。

进程响应信号的方式有3种，忽略、捕捉、和执行默认操作。

Linux对每一个标准信号都有默认的操作方式。针对不同种类的标准信号，其默认的操作方式一定会是以下操作之一：终止进程、忽略该信号、终止进程并保存内存信息、停止进程、恢复进程(若进程已停止)

socket

socket，常译为套接字，也是一种IPC方法。但是与其他IPC方法不同的是，它可以通过网络连接让多个进程建立通信并相互传递数据，这使得通信双方是否在同一台计算机上变得无关紧要。实际上，这是socket的目标之一，使得通信端的位置透明化。

socket基本特性

在linux系统中，存在一个名为socket的系统调用

int socket(int domain, int type, int protocol)

该系统调用用于创建一个socket实例。它接受3个参数，分别代表这个socket的通信域、类型和所用协议

通信域包含三种：

IPv4域 - 基于IPv4协议的网络中任意两台计算机上的应用程序
IPv6域 - 基于IPv6协议的网络中任意两台计算机上的应用程序
Unix域 - 同一计算机上的两个应用程序

线程

线程可以视为进程中的控制流，一个进程至少会包含一个线程。因为其中至少会有一个控制流持续运行。因而，一个进程的第一个线程会随着这个进程的启动而创建，这个线程称为该进程的主线程。当然，一个进程也可以创建多个线程。这些线程都是有当前已存在的线程创建出来的。创建的方法就是系统调用，更准确的说是调用pthread_create函数。拥有多个线程的进程可以并发执行多个任务，并且即使某个或某些任务被阻塞，也不会影响其他任务正常执行。另一方面，线程不可能独立与进程存在。它的生命周期不可能超过所属进程的生命周期。

进程中所有线程都有自己的线程栈，存储自己的私有数据。这些线程栈都包含在进程的虚拟内存地址中。同时，一个进程中的很多资源读会被其中的所有线程共享，这些被线程共享的资源包括在当前进程的虚拟内存地址中存储的代码段、数据段、堆、信号处理函数。所以，同一进程中的多个线程运行的一定是同一个程序，只不过具体的控制流程和执行的函数可能会不同。另外，创建一个新线程也不会像创建一个新进程那样耗时费力，因为在其所属的进程的虚拟内存地址中存储的代码、数据、和资源都不需要复制。

线程的标识

和进程(pid)一样，每个线程也有自己的ID，称为TID。与进程不同，线程ID不需要保证系统范围内的唯一，只需要在所在进程范围内唯一就行了。但是，linux系统的线程实现则确保了每个线程ID在其系统范围内的唯一，并且，当线程不存在时，其线程ID可以被其他线程复用。

线程ID是由操作系统内核分配和维护的。

线程之间的控制

// 创建线程
同一进程的多个线程的层级不像进程之间有明确的所属关系，它们是平级的。除了主线程随进程的启动而创建外，其他线程都可以通过pthread_create来创建新的线程。

// 终止线程
也可以通过多种方式终止同一进程的其他线程(如: pthread_cancel)。

// 连接已终止的线程
可以通过多种方式连接已终止的线程(pthread_join)。调用线程会一直等到线程ID对应的那个线程终止，并把该线程执行的start函数的返回值告知调用线程。当目标线程把流程控制权交出时，调用线程会接过流程控制权并继续执行pthread_join函数调用之后的代码。如果一个线程可以被连接，那么在它结束的时候就必须连接，以便后续执行其他的线程，否则就会创建一个僵尸线程。僵尸线程不但会导致系统资源浪费，还会无意义地减少所属进程的可创建线程数量。比如，main线程调用pthread_join函数，等待新开的线程执行结束。

// 分离线程
默认情况下，一个线程总可以被其他线程连接。分离操作的将其变为不可连接的线程，同时，让操作系统内核在目标线程终止时自动进行清理和销毁工作。

线程的调度

调度器会把时间划分为极小的时间片并把这些时间片分配给不同的线程，以使众多线程都有机会在CPU上运行。

线程的执行总是趋向于CPU受限或I/O受限。换句话说，一些线程需要话费一定时间使用CPU进行计算，而另外一些线程则会花费一些时间等待相对较慢的I/O操作的完成。通常，调度器会依据趋向性猜测，将其分类，并让I/O受限的线程具有更高的动态优先级以有限使用CPU。因为调度器任务I/O操作一般会花费更多的时间，因此应该早点执行。

线程的动态优先级是可以被调度器实时调整的，而与之对应的静态优先级则只能由应用程序指定。如果未指定，则设定为0。动态优先级就是调度器在静态优先级的基础上调整得来的。动态优先级在运行顺序上起到来关键作用，静态优先级则决定来线程单次在CPU上执行的最长时间，也就是调度器分配给它的时间片的大小

内核会为每一个CPU创建一个运行队列，所有等待使用CPU的线程会按照动态优先级从高到低的顺序排列，并依序放到与CPU对应的运行队列中。因此，下一个运行的线程总是动态优先级最高的那一个。实际上，每一个CPU的运行队列中都包含两个优先级阵列：其中一个用于存放正在等待运行的线程，假定为A;另一个用于存放已经运行过但还未完成的线程，假定为B;确切的来说，优先级阵列是一个由若干个链表组成的数组，一个链表只会包含具有相同优先级的线程，而一个线程也只会放到与其优先级相对应的那个链表中。当一个线程放入某个优先级阵列时，实际上就是放到了与其优先级相对应的链表的末尾。

下一个运行的线程总是会从激活的优先级阵列(A)选出，若调度器发现某个线程已经占用了CPU很长时间(该时间小于等于给予该线程的时间片)，并且激活的优先级阵列中还有优先级与它相同的线程在等待运行，那么调度器就会让那个等待的线程在CPU上运行，而被换下的线程会放入B,当激活的优先级阵列中没有待运行的线程时，调度器会把这两个优先级阵列身份呼唤，即之前的激活的A变为B。这样B中的线程又有机会执行了。

线程不会总是在就绪状态和运行状态，它还有可能因阻塞而进入睡眠状态。它们会从运行队列中移除。

线程会因为某个事件或条件的发生而加入到对应的等待队列中，当条件满足后，内核会唤醒等待队列中的所有线程，这些线程会移至适当的运行队列中。

调度器还会负责多个CPU之间的负载平衡。尽量使同一个线程在一个特定的CPU上运行。这样可维持高速缓存的命中率以及高效使用就近的内存等等。每个运行队列都会保存对应的CPU的负载系统，调度器会根据此系数去进行平衡调度，或线程在CPU运行队列之间的迁移。

线程的实现模型

线程的实现模型主要有3个，分别是：用户级线程模型、内核线程模型和两级线程模型。它们之间最大的差异就在于线程内核调度实体之间的对应关系上。内核调度实体就是可以被内核的调度器调度的对象。是操作系统内核的最小调度单元。

用户级线程模型
1. 此模型下的线程是由用户级别的线程库管理的。线程库不是内核的一部分，而只是存储在进程的用户空间中。对线程的管理和协调完全是用户线级程序的自主行为，与内核无关。所以应用程序对线程进行创建、终止、切换或同步的操作并不需要让CPU从用户态切换到内核态。
2. 由于对线程的管理不需要内核参与，有些事儿就不能真正的并发执行。比如：如果一个线程在I/O操作中被阻塞，那么其所属进程也会被阻塞。因为对调度器来说，进程就是无法被分割的调度单元，无论其中有多少个线程。
3. 基于上述问题，当代操作系统都不适用这种模型来实现线程。由于包含来多个用户线程的进程只与一个KSE(内核调度实体)相对应，因此这种线程实现模型又称为多对一 (M:1)的线程实现
内核级线程模型
1. 该模型下的线程是由内核负责管理的，他们是内核的一部分。应用程序对线程的创建、终止和同步都必须通过内核提供的系统调用来完成。进程中每一个线程都与一个KSE相对应。因此称为一对一的线程实现。
2. 此模型使得线程实现了真正的并发，但是使得内核压力增大，创建、切换等操作会用到更多的内核资源，时间花费得更多。基于此，内核级线程模型中对一个进程创建的线程会有数量限制。
3. Linux系统就是这种模型。
两级线程模型
1. 两级线程模型是上述两种的综合，称为(M:N)的线程实现。此模型下，一个进程可以与多个KSE相关联，这与内核级线程模型相似。但是不同的是，进程中的线程并不与KSE一一对应。
2. 首先，实现两级线程模型的线程库会通过操作系统内核创建多个内核级线程。然后，通过这些内核级线程对应用程序的线程进行调度。大多数此类线程库都可以将这些应用程序线程动态地与内核级线程关联。这样会使得线程管理的难度增大，更加复杂。但是带来的好处是内核资源消耗降低，并且对应用程序线程的管理效率提升。就此而言，操作系统往往不会被使用此中线程模型。但是，这样的模型确可以很好的适用在编程语言上。Go语言的并发编程模型就和两级线程模型的理念非常相似。

互斥量

在同一时刻，只允许一个线程处于临界区之内的约束称为互斥。每个线程在进入临界区之前，就必须先锁定某个对象，只有成功锁定对象的线程才会允许进入临界区，否则就会阻塞，这个对象称为互斥对象或互斥量。

由此可知，互斥量有两种可能的状态，即已锁定状态和未锁定状态。互斥量每次只能锁定一次。只有拥有此互斥量的对象才能对此互斥量进行解锁。线程在离开临界区的时候，必须要对应的互斥量进行解锁。这样其他的线程才能获取。同时，对一个互斥量的加锁和解锁的操作应成对出现。不能重复加锁或解锁。

类比Go语言的syc.mutex，java中的 Synchronized

使用注意:

对互斥量的初始化必须要保证唯一性
线程在离开临界区的时候必须要及时解锁

解决或避免死锁的方法

使用操作系统所提供的线程库的功能 - 试锁定-回退

若发生了需要锁定多个互斥量的情况，它会先试着去锁定一个互斥量，之后使用试锁定的方法去锁定另一个互斥量，如果锁定失败，就释放前面锁定的互斥量

顺序锁定

若发生需要锁定多个互斥量的情况，需要一次锁定，比如，先锁定A，再锁定B，这种固定顺序锁定也能避免死锁的可能。这种方法在不知道线程锁定多个互斥量的情况下会出现问题

所以。在确定互斥量锁定顺序的情况下使用固定顺序锁定，不确定的时候使用试锁定-回退方法。