4.1进程、线程基础知识

进程

代码是存储在硬盘的静态文件，编译后生成可执行文件，可执行文件运行后被装载到内存中，这个运行中的程序被称为进程（Process）。

么当运行到读取⽂件的指令时，就会去从硬盘读取数据，但是硬盘的读写速度是⾮常慢的，那么在这个时候，如果 CPU 只等硬盘返回数据别的什么都不做，那 CPU 的利⽤率是⾮常低的。所以当读取硬盘数据时CPU不需要阻塞等待而是会去执行其他进程，当硬盘数据返回时CPU会收到一个中断，然后CPU继续做运行这一进程。

一个支持多进程的系统，CPU会从一个进程快速切换至另一进程每个执行几十几百毫秒，单核CPU在某一瞬间只能运行一个进程，但一秒内运行多个进程给人并行的错觉，实际上这是并发。

进程的状态

⼀个进程的活动期间⾄少具备三种基本状态，即运行状态、就绪状态、阻塞状态。

运行状态：占用CPU
就绪状态：其他进程在运行状态
阻塞状态：因等待某一事件发生后而暂停运行，即便占有CPU也无法运行

此外还有创建状态（进程正在被创建时的状态）和结束状态（进程正在从系统中消失时的状态）

进程状态跃迁

NULL -> 创建状态：⼀个新进程被创建时的第⼀个状态；
创建状态 -> 就绪状态：当进程被创建完成并初始化后，⼀切就绪准备运⾏时，变为就绪状态，这个过程是很快的，然后进入就绪队列；
就绪态 -> 运⾏状态：处于就绪状态的进程被操作系统的进程调度器选中后，就分配给 CPU 正式运⾏该进程；
运⾏状态 -> 结束状态：当进程已经运⾏完成或出错时，会被操作系统作结束状态处理；
运⾏状态 -> 就绪状态：处于运⾏状态的进程在运⾏过程中，由于分配给它的运行时间片用完，操作系统会把该进程变为就绪态，接着从就绪态选中另外⼀个进程运⾏；
运行状态 -> 阻塞状态：当进程请求某个事件且必须等待时，例如请求 I/O 事件；
阻塞状态 -> 就绪状态：当进程要等待的事件完成时，它从阻塞状态变到就绪状态

如果有大量处于阻塞状态的进程，进程就可能占用物理内存空间，所以在虚拟内存管理的操作系统中通常会把阻塞状态的进程从物理内存空间换到硬盘，需要运行时再换入内存。此时没有占用实际物理内存空间的状态称为挂起状态，挂起状态有两种：阻塞挂起状态和就绪挂起状态，阻塞挂起状态等到事件发生之后是变成就绪挂起状态而不是直接进入就绪状态

进程的控制结构

在操作系统中，是⽤进程控制块（process control block，PCB）数据结构来描述进程的。

PCB 是进程存在的唯⼀标识，具体包括

进程描述信息：进程标识符（每个进程都有且唯一）和用户标识符（进程归属用户，为共享和保护服务）
进程控制和管理信息：进程当前状态（new、ready、running、waiting 或 blocked）和进程优先级
资源分配清单：有关内存地址空间或虚拟地址空间的信息，打开文件列表，I/O设备信息
CPU相关信息：寄存器的值，CPU状态信息（进程重新执行时能从断点处执行）

PCB通常通过链表方式组织，把具有相同状态的进程链在一起组成各种队列，比如就绪队列、阻塞队列，在单核CPU中则只有一个运行指针。除了链接的组织方式还有索引方式，将同一状态的进程组织在一个索引表中，索引表项指向相应的PCB，不同状态对应不同索引表，但是链表比较好，因为进程可能面临创建你销毁等情况，链表能更灵活的插入删除

进程的控制

进程的创建、终⽌、阻塞、唤醒的过程，这些过程也就是进程的控制

创建进程

操作系统允许一个进程创建另一个进程并继承父进程所拥有的资源，子进程被终止时继承的资源要还给父进程，终止父进程也会终止所有子进程。

创建进程过程如下：

为新进程分配一个唯一的进程标识号，并申请一个空白的PCB，PCB是有限的
为进程分配资源，资源不足则进入等待状态
初始化PCB
如果调度队列能够接纳新进程，新进程则插入就绪队列，等待被调度

终止进程

进程三种终止方式：正常结束、异常结束、外界干预（kill）

终止过程：

查找要终止的PCB
如果处于执行状态，则终止进程的执行并将CPU资源分配给其他进程
如果有子进程则全部停掉
把该进程所拥有的全部资源归还父进程或操作系统
将其从PCB所在队列中删除

阻塞进程

找到相应进程的PCB
如果该进程在运行则保护好现场，将状态转为阻塞停止运行
把该PCB插入阻塞队列

唤醒进程

阻塞进程是不会自己叫醒自己的，只有该进程所期待的事情发生的时候，才有发现者用唤醒语句 / 别的进程发消息给它来唤醒

唤醒过程：

找到相应进程的PCB
将其从阻塞队列中移除，并将状态置为就绪状态
把PCB插入就绪队列等待调度

进程的上下文切换

从一个进程切换到另一个进程，称为进程的上下文切换

任务通常是并发的，每个任务运行前CPU要知道从哪里加载从哪里开始运行，所以操作系统需要事先帮CPU设置好CPU寄存器和程序计数器。CPU寄存器是一个容量小速度极快的内存，程序计数器用来存储CPU正在执行的指令的位置或者即将执行的下一条指令的位置，CPU寄存器和程序计数是CPU在运行任何任务前所必须依赖的环境，这些环境就叫做CPU上下文。

CPU上下文切换即是把上一个任务的CPU上下文保存起来，加载新任务的上下文到寄存器和程序计数器，运行新任务。系统内核会存储保持上下文信息，当运行某一任务时就加载对应的上下文，保证任务原状态不受影响。此时任务主要包含进程、线程和中断，可以根据任务不同把CPU上下文切换分成进程上下文切换、线程上下文切换和中断上下文切换。

进程由内核管理调度，进程的切换只能发生在内核态。进程上下文切换不仅包含虚拟内存、栈、全局变量等用户空间资源，还包括内核堆栈、寄存器等内核空间资源。通常会把交换的信息存在进程的PCB中，从PCB存取上下文。

发生进程上下文切换的常见场景

CPU时间被分为一段段时间片，时间片被轮流分给进程，时间片耗尽进程则从运行状态变成就绪状态，换一个进程运行
进程资源不足时也会被挂起，系统调度其它进程运行
通过sleep函数将进程主动挂起时，自然也会重新调度
当有更高优先级进程时，当前进程会被挂起
发生硬件中断时CPU上的进程会被中断挂起，转而执行内核中的中断服务程序

线程

更小的能独立运行的基本单位，也就是线程。可以并发运行，共享相同的地址空间。

线程是进程当中的一条执行流程。同一进程的多个线程之间可以共享一些资源如代码段、数据段、打开的文件等，但拥有独立的寄存器和栈，由此确保进程相对独立。

当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃。

进程线程比较

进程是资源分配单位，线程是CPU调度单位
进程拥有完整资源，线程独享必不可少的资源如寄存器和栈
线程也具有就绪阻塞执行三种状态
线程能减少并发执行的时间和空间开销

线程相比进程减少开销体现：

线程创建快，因为进程创建要资源管理信息，线程可以直接共享
线程终止快因为释放资源少
线程切换快，因为地址空间是相同的（共享），用的是同一个页表
线程之间传递数据不需要通过内核，因为共享

最大区别：线程是调度的基本单位，而进程则是资源拥有的基本单位。操作系统任务调度实际上调度的是线程，进程只是给线程提供了虚拟内存、全局变量等资源

线程上下文切换

当进程拥有多个线程时，这些线程共享的相同的资源，在线程上下文切换时不需要修改保持不动，但栈和寄存器这种私有数据在切换中是需要保存的，因此开销小很多。属于不同进程的线程之间切换时，就跟进程上下文切换相同。

线程的实现

主要有三种线程实现方式：

用户线程：在用户空间实现，由用户态线程库进行线程管理
内核线程：内核中实现，由内核管理
轻量级进程：内核中用来支持用户进程

用户线程和内核线程存在多对一、一对一和多对多的关系。

一对一：为每一个用户态的线程分配一个单独的内核态线程，实现起来简单但开销较大，对用户线程的操作大部分会映射到内核线程上引起用户态和内核态的频繁切换。
多对一：因为用户现场对内核来说是透明的，所以不需要内核态和用户态切换，线程的创建调度同步非常快。由于多个用户现场对应到同一内核线程，一个阻塞会导致其他也无法执行。内核也不知道用户线程是怎么样的，无法实现完整调度、优先级等。库调度器选择一个用户线程和一个内核线程关联起来。

用户线程（多对一模型）

用户线程基于用户态线程库来实现，线程控制块（TCB）也是在库中实现的，对操作系统而言只看得到PCB而看不到TCB（不可见性、透明性）。所以用户线程的整个线程管理和调度，操作系统是不直接参与的，而是用户级线程库函数来完成线程的管理，包括线程的创建、终止、同步和调度。

用户线程优点：每个进程都需要有它私有的TCB列表，用来跟踪记录各个线程状态信息，TCB由用户级线程库函数维护，可用于不支持线程技术的操作系统。线程切换也由用户级线程库完成，无需用户态和内核态切换。

用户线程缺点：如果一个线程发起了系统调用而阻塞，那么同一进程的其他线程都不能执行了。用户态线程无法打断当前运行的线程，只有操作系统有这个权限，但用户态线程不由操作系统管理。时间片是分配给进程的，因此多线程时每个线程获得的时间片较少。

任由线程阻塞操作会影响进程的效率，可以通过jacket把产生阻塞的系统调用变成非阻塞的系统调用，比如检查IO设备是不是在忙，在忙的话先把控制权交给另一个线程，隔一段时间后再检查IO设备。

内核线程（一对一映射）

由操作系统管理，对应的TCB在操作系统中，由操作系统进行管理如创建、终止、调度等。

内核线程的优点：如果某个内核线程发起系统调用而被阻塞。不会影响其他内核线程的运行；分配给线程，多线程的进程获得更多的CPU时间

内核线程的缺点：由内核来维护进程线程的上下文信息。创建终止切换通过系统调用进行，开销较大。

轻量级进程（Light-weight process，LWP）

内核支持的用户进程，一个进程可有一个或多个LWP，每个LWP是跟内核线程一对一映射的，也就是LWP都是由一个内核线程支持。LWP由内核管理并像普通进程一样被调度。

在大多数系统中LWP与普通进程的区别在于它只有一个最小的执行上下文和调度程序所需的统计信息，不像进程一样需要那么多的状态信息。

LWP之上也是可以使用用户线程的，同样有1：1，1：N，M：N的关系，1：1则实现并行，不影响其他的LWP，但创建线程开销较大；1：N时用户开几个线程都没关系，且切换效率较高，但如果一个用户线程阻塞会导致整个进程阻塞；M：N是前两个模型调度混搭，结合了前两者的优点且可以利用多核CPU；组合模式以上的几种模式在进程中结合起来使用，开发⼈员可以针对不同的应⽤特点调节内核线程的数⽬来达到物理并⾏性和逻辑并⾏性的最佳⽅案

调度

选择一个进程运行由操作系统完成，通常称为调度程序

调度时机

当进程的状态发生变化，从运行状态变为其他状态或者从其他状态变为运行状态时，会触发操作系统的调度，因为当这些状态变化发生时操作系统要考虑是否让进程给CPU运行或者让进程从CPU上退下来。

根据硬件时钟提供某个频率的周期性中断，可以根据如何处理时钟中断把调度算法分为两类：

非抢占式调度算法：挑选一个进程运行到被阻塞或者退出，不理会时钟中断
抢占式调度算法：让进程只运行某段时间，该时段结束后则挂起换另一个进程来，此调度处理需要在时间间隔末端发生时钟中断，把CPU控制返回给调度程序，也就是时间片机制。

调度原则

为了提高CPU利用率，在CPU空闲时调度程序会从就绪队列选一个进程来运行
为了提高系统的吞吐率，调度程序要权衡长任务和短任务进程的运行完成数量
从进程开始到结束实际包含进程运行时间和进程等待时间，两者总和称为周转时间，调度程序应避免出现进程等待时间很长而运行时间很短导致周转时间很长的情况
应考虑就绪队列中进程的等待时间
交互式较强的应用（如鼠标键盘）应考虑其响应时间

由此可概况出：CPU利用率，系统吞吐量，周转时间，等待时间和响应时间五个原则

调度算法

在单核CPU中：

先来先服务（FCFS）：非抢占式，直到进程阻塞或退出才从队列选择第一个进程运行
最短作业优先（Shortest Job First，SJF）：优先选择运行时间最短的进程来运行，对长作业不利
高响应比优先调度算法（Highest Response Ratio Next, HRRN）：进行进程调度时先计算相应比优先级（（等待时间 + 要求服务时间）/ 要求服务时间），然后把相应比优先级最高的进程先投入运行
时间片轮转（Round Robin, RR）：允许进程在分配的时间段中运行。如果时间片用完进程还在运行，就把进程从CPU中释放出来，把CPU分配给其他进程；如果进程在时间片结束前阻塞或结束则立即切换。时间片长度一般设为20ms ~ 50ms
最高优先级（Highest Priority First，HPF）调度算法：优先级可以分为静态和动态。在动态优先级中，进程会随着时间的推移增加而优先级提升。该算法也分抢占式和非抢占式，非抢占式则即便就绪队列出现更高优先级的进程也先运行完当前的，抢占式则当发现就绪队列有优先级高的进程时，就把当前进程挂起换优先级高的进程运行。
多级反馈队列（Multilevel Feedback Queue，MFQ）调度算法：时间片轮转算法和最高优先级算法的综合和发展。多级表示多个队列，每个队列有其优先级，优先级越高时间片越短。反馈表示如果有新的新城加入优先级高的队列时，立即停止当前运行的进程，去运行优先级高的队列。

新的进程会被放入第一级队列（优先级最高）的末尾按先来先服务的原则等待被调度，如果在第一级队列规定的时间片没运行完成则转入第二级队列的末尾，直到完成。当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。当有新进程进入优先级较高的队列时，则停止当前的进程并将其移到队列末尾，让较高优先级的进程先运行

4.2进程间通信

管道

Linux中的竖线丨就是一个管道，竖线前的命令的输出作为竖线后命令的输入，管道传输数据是单向的，如果要相互通信的话需要创建两个管道

竖线丨没有名字，用竖线表示的管道称为匿名管道，用完就销毁。还有一种命名管道，被叫做FIFO，因为数据是先进先出的传输方式

使用命名管道前通过mkfifo来创建并指定名字，基于Linux一切皆文件的理念，管道是p类型的文件（pipe）。管道这种通信方式效率低，不适合进程间频繁地交换数据。对于命名管道，不相关的进程之间也能相互通信。

匿名管道创建可以通过以下系统调用int pipe(int fd[2])，管道读取端描述符fd[0]，管道写入端描述符fd[1]，此特殊文件只存在于内存中。所谓管道就是内核里的一串缓存，从一端写入后缓存在内核中，另一端也是从内核中读取。管道传输的数据无格式且大小受限。

但实际上这两个描述符都在一个进程里，我们通过fork创建子进程，创建的子进程会复制父进程的文件描述符，这样两个进程有各自的fd[0]和fd[1]，但写入和读取的是同一个管道文件，因此也实现了跨进程通信。为了保证只能一端写入一端读出而不会混乱，通常的做法是：父进程关闭读取的 fd[0]，只保留写入的 fd[1]；子进程关闭写入的 fd[1]，只保留读取的 fd[0]；如果要双向通信的话就创建两个管道。

消息队列

管道通信方式效率低，不适合进程间频繁地交换数据。消息队列的通信方式可以解决此问题，要发送时把数据放在对应的消息队列即可返回，要读取时进程去读取即可。

消息队列是保存在内核中的消息链表，在发送数据时会分成一个一个独立的数据单元，也就是消息体（数据块），消息体是用户自定义的数据类型，因此收发方药约定好消息体的数据类型。每个消息体是大小固定的存储块，而不是管道中无格式的字节流。消息体被读取之后就会被内核删除。

消息队列如果没有被释放或者操作系统没有关闭，消息队列就会一直存在。匿名管道的生命周期和进程一致。

消息队列不足之处在于：通信不及时，附件大小有限制。消息队列不适合比较大的数据的传输，因为消息体有最大长度限制MSGMAX，队列包含信息体的总长度也有上限MSGMNB。

消息队列通信过程中存在用户态和内核态之间的数据拷贝开销。进程写入数据到内核中的消息队列时会发生用户态拷贝数据到内核态的过程，读取时会发生一个相反的过程。

共享内存

解决了用户态与内核态之间的消息拷贝的过程。共享内存的机制是拿出一块虚拟地址空间出来，映射到相同的物理内存中。

信号量

多进程如果同时修改一个共享内存很可能会冲突，因此需要保护机制防止多进程竞争共享资源造成数据错乱，使得共享的资源在任意时刻只能被同一个进程访问。

信号量是一个整型的计数器，主要用于实现进程间的互斥与同步，而不是用于缓存你进程间通信的数据。信号量表示资源的数量，控制信号量的方式有两种原子操作：

P操作：信号量-1，如果信号量之后小于0则表明资源已经被占用，进程阻塞等待，如果大于等于0表示还有资源可用
V操作：把信号量加上1，如果之后信号量小于等于0则说明有阻塞中的进程，会将其唤醒运行

如果要使两个进程互斥访问共享内存，我们可以初始化信号量为1，代表着互斥信号量，保证共享内存在任意时刻只有一个进程在访问。

如果要实现多进程同步的方式，我们可以初始化信号量为0，代表着同步信号量。如果读取数据进程先执行时执行P操作，由于初始是0，之后变成-1，表示生成数据进程还没生成，读取进程阻塞等待。当生成数据进程结束后执行V操作，使得信号量变成0，唤醒读取数据进程。

信号

对于异常情况下的工作模式需要用到信号的方式来通知进程。信号事件注意要来源有硬件来源（如Ctrl + C）和软件来源（如kill），信号是进程间通信机制中唯一的异步通信机制。（反正是异步的）

一旦有信号产生，会有以下几种信号处理方式：

执行默认操作
捕捉信号，执行相应信号处理函数（可以自己定义）
忽略，但是有些信号无法捕捉和忽略比如SIGKILL和SEGSTOP

Socket

跨网络跨主机上的进程的通信需要用到Socket

int socket(int domain, int type, int protocal)

domain参数指定协议簇（⽐如 AF_INET ⽤于 IPV4、AF_INET6 ⽤于 IPV6、 AF_LOCAL/AF_UNIX ⽤于本机）
type参数指定通信特性（SOCK_STREAM 表示的是字节流，对应 TCP、 SOCK_DGRAM 表示的是数据报，对应 UDP、SOCK_RAW 表示的是原始套接字；）
protocal 参数原本是⽤来指定通信协议的，现在一般写成 0 即可

针对 TCP 协议通信的 socket 编程模型

服务端

初始化服务端和客户端socket，得到文件描述符
服务端调用bind绑定ip和端口
调用listen监听
调用accept等待客户端连接
调用read读取数据

客户端

调用connect向服务器地址和端口发起连接请求
调用write写入数据

客服端断开连接用close，服务端会读取到EOF，处理完后服务端调用close表示连接关闭

服务端调用accept时，连接成功了会返回一个已完成连接的socket用来传输数据，使用监听的socket和传输的socket是两个socket，一个叫监听socket，一个叫已完成连接socket，连接建立后通过read和write来读写数据

针对 UDP 协议通信的 socket 编程模型

UDP没有连接，不需要三次握手也不需要listen和connect，但交互仍然需要IP和port，所以也要bind，每一个socket的都需要bind

针对本地进程间通信的 socket 编程模型

用于同一台主机上进程间的通信，本地socket的编程接口和IPv4、IPv6套接字编程接口一致，可支持字节流和数据报两种协议，且实现效率更高。在bind的时候不用绑定IP和port，而是绑定一个本地文件。

总结

匿名管道没有名字标识，如Linux中的竖线丨，通信的数据是无格式的流且大小受限，是单向的，且只能用于父子关系的进程间通信

命名管道可以在无亲缘关系的进程之间通信。管道通信都是先把数据写入缓存到内核，读取也是从内核中获取，遵循先进先出原则。

消息队列通过一个个独立消息体，实际上是保存在内核的消息链表，收发方要保证消息体数据类型一致。每次数据写入读取都要通过用户态和内核态之间的拷贝。

共享内存直接分配一个共享空间，每个进程都能直接访问，是最快的进程通信方式，但可能出现多进程竞争同个共享资源造成数据错乱

信号量可以保护共享资源，实际上是个计数器表示资源个数，通过PV两个原子操作来控制。不仅可以实现访问的互斥性，还能实现进程间的同步。

信号是进程间唯一的异步通信机制，主要来源有软件和硬件，进程有三种方式相应信号。

不同主机进程间通信要用到socket，但此法也可以用于本地主机的进程间通信。分为三种常⻅的通信⽅式，⼀个是基于 TCP 协议的通信⽅式，⼀个是基于 UDP 协议的通信⽅式，⼀个是本地进程间通信⽅式。

信号量也同样可以在线程间实现互斥与同步：互斥的方式可保证任意时刻只有⼀个线程访问共享资源；同步的方式，可保证线程A 应在线程 B之前执行；

4.3多线程同步

竞争与协作

每个进程用一个时间片，时间片⽤完了，就切换下⼀个进程运行，由于这个时间片的时间很短，于是就造成了「并发」的现象。

操作系统也为每个进程创建巨大、私有的虚拟内存的假象，这种地址空间的抽象让每个程序好像拥有⾃⼰的内存，⽽实际上操作系统在背后秘密地让多个地址空间「复用」物理内存或者磁盘。

互斥的概念

当多线程相互竞争操作共享变量时，可能在执行过程中发⽣了上下⽂切换，我们得到了错误的结果，而事实上每次操作都可能出现不同结果，因此输出的结果存在不确定性。

访问共享资源的代码片段我们称为临界区，这段代码一定不能给多线程同时执行。我们希望这段代码是互斥的，也就是说保证一个线程在临界区执行时，其他线程应该被组织进入临界区。

同步的概念

互斥解决了并发进程 / 线程对临界区的使用问题。这种基于临界区控制的交互作用是比较单调的，只要一个进入了临界区，其他想进入的都会被阻塞直到进入临界区的进程 / 线程离开。

多线程中每个线程不一定是顺序执行的，它们各自独立各自推进，但有时我们又希望多个线程能密切合作以实现一个共同的任务。

所谓同步，就是并发进程 / 线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程 / 线程同步。

互斥与同步的实现和使用

进程 / 线程之间存在协作的关系，例如互斥同步，为了实他们之间正确的协作，操作系统必须提供实现进程协作的措施和方法，主要方法有：加锁解锁操作和P、V操作

锁

通过加锁解锁操作解决并发线程 / 进程的互斥问题。想进入临界区必须先执行加锁操作，加锁成功后才能进入临界区，对临界资源进行访问，之后再执行解锁操作以释放临界资源。

根据锁实现的不同可以分为忙等待锁和无忙等待锁。

原子操作：要么全部执行，要么全部不执行，不能出现执行到一半的中间状态。

忙等待锁：当获取不到锁时，线程一直在while循环等到拿到锁为止，不做任何事情，也被称为自旋锁。自旋锁在单处理器上需要抢占式的调度器（即会通过时钟中断线程，运行别的线程），否则自旋锁在CPU上无法使用，因为一个自旋的线程永远不会放弃CPU。

无等待锁：获取不到锁的时候，不用自旋，而是把该线程放入锁的等待队列，然后执行调度程序，把CPU让给其他线程执行。

信号量

信号量是操作系统提供的一种协调共享资源访问的方法。通常信号量表示资源的数量，对应的变量是一个整型变量。另外还有两个原子操作的系统调用函数来控制信号量，这两个操作必须成对出现

P操作：将信号量-1，如果相减后小于0，进程 / 线程就阻塞等待
V操作：将信号量+1，如果相加后小于等于0，就唤醒一个等待中的进程 / 线程

信号量既可以实现临界区的互斥访问，也可以实现进程间的事件同步。

实现互斥：将信号量初值设为1表示该临界资源未被占用，对于两个并发进程互斥信号量取值只有0（有⼀个线程进⼊临界区），1（表示没有线程进⼊临界区），-1（表示⼀个线程进⼊临界区，另⼀个线程等待进⼊）

实现同步：设置信号量为0，一个进程进行P之后变成-1开始等待，另一个进程V之后说明之前的进程可以执行相关的操作了

⽣产者-消费者问题

生产者生成数据后放入缓冲区中，消费者从缓冲区中取出数据处理，任何时刻只能有一个生产者或消费者访问缓冲区。缓冲区满时，⽣产者必须等待消费者取出数据。说明⽣产者和消费者需要同步。任何时刻只能有⼀个线程操作缓冲区，说明操作缓冲区是临界代码，需要互斥

所以需要三个信号量，互斥信号量mutex，资源信号量fullBuffers，资源信号量emptyBuffers。

经典同步问题

哲学家就餐

方案1

假设五位哲学家同时拿起左边的叉⼦，拿了左边的就要去拿右边的，桌⾯上就没有叉子了，很明显这发⽣了死锁的现象

方案2

在拿叉⼦前，加个互斥信号量，哲学家进⼊了「临界区」，也就是准备要拿叉⼦时，其他哲学家都不能动，只有这位哲学家⽤完叉⼦了，才能轮到下⼀个哲学家进餐，但效率低

方案3

即让偶数编号的哲学家「先拿左边的叉⼦后拿右边的叉⼦」，奇数编号的哲学家「先拿右边的叉⼦后拿左边的叉⼦」

⽅案4

用⼀个数组 state 来记录每⼀位哲学家在进程、思考还是饥饿状态（正在试图拿叉⼦），⼀个哲学家只有在两个邻居都没有进餐时，才可以进⼊进餐状态。进入这个判定时需要mutex，判定结束后就释放让其他的哲学家也可以判定

读者-写者问题

允许多个读者同时读；没有写者时才能读，没有读者时才能写；没有其他写者时才能写

方案1

控制写操作的互斥信号量wMutex，初始值1
读者计数rCount，初始值0
信号量rCountMutex，初始值1

是读者优先的策略，只要有读者在读后面的读者可以直接进入，写者可能会饥饿

方案2

有写者要写入，后来的读者就阻塞，如果有写者持续不断写入则读者饥饿

信号量 rMutex ：控制读者进⼊的互斥信号量，初始值为 1；
信号量 wDataMutex ：控制写者写操作的互斥信号量，初始值为 1；
写者计数 wCount ：记录写者数量，初始值为 0；
信号量 wCountMutex ：控制 wCount 互斥修改，初始值为 1

在写者写的时候如果写者数量为0，就对rMutex进行p操作锁住，不允许读者进来除非没有写者了，是写者优先的策略

方案3

公平策略

设置rCountMutex控制对Rcount互斥修改，初始值为1
设置wDataMutex，控制写者写操作的互斥量，初始值为1
设置flag用于公平竞争，初始值为1
设置rCount来统计读者个数

写者只申请flag和wDataMutex；读者也申请flag，同样当读者开始进入时就申请wDataMutex阻塞写者操作，修改完rCount就释放flag。因此后续的读者要读的时候，申请不到flag，无法进入读的状态，等到已经在读的读者读完1之后就会释放wDataMutex。因此对读者和写者而言都是公平的。

4.4死锁

概念

这两个互斥锁应用不当的时候，可能会造成两个线程都在等待对⽅释放锁，在没有外⼒的作⽤下，这些线程会⼀直相互等待，就没办法继续运⾏，这种情况就是发⽣了死锁

死锁只有同时满⾜以下四个条件才会发⽣：

互斥条件：多个线程不能同时使⽤同⼀个资源
持有并等待条件：持有资源1等待资源2时不会释放资源1
不可剥夺条件：在⾃⼰使⽤完之前不能被其他线程获取
环路等待条件：两个线取资源的顺序构成了环形链。

利用工具排查死锁

Java 程序是否死锁，则可以使⽤ jstack ⼯具，它是jdk⾃带的线程堆栈分析⼯具

在 Linux 下，我们可以使⽤ pstack + gdb ⼯具来定位死锁问题

避免死锁发生

产生死锁的四个必要条件：互斥条件，持有并等待条件，不可剥夺条件，环路等待条件。避免死锁只需要破坏其中一个条件，最常见且可行的就是使用资源有序分配法来破坏环路条件

资源有序分配法：比如线程A和线程B都需要资源a和资源b，那么则保证A和B都是以a，b的顺序获取资源

4.5悲观锁和乐观锁

高并发的场景下，如果选对了合适的锁，则会大大提高系统的性能，否则性能会降低。

最常用的锁是互斥锁，也有很多种不同的锁比如自旋锁、读写锁、乐观锁、悲观锁等。

互斥锁和自旋锁

互斥锁加锁失败后，线程会释放CPU给其他线程；

对于互斥锁加锁失败而阻塞的现象，是由操作系统内核实现的。加锁失败时，内核会将线程设置为睡眠状态，等到锁被释放后，内核会在合适的时机唤醒线程，当线程获取到锁后就可以继续执行。因此，互斥锁加锁失败会从用户态陷入到内核态，让内核帮忙切换线程，但会有性能开销

会有两次线程上下文切换的成本：当加锁失败，内核将线程从运行状态设置为睡眠状态，然后把CPU切换给其他线程；当锁释放，睡眠状态的线程会变为就绪状态，内核会在合适的时间把CPU切换给线程运行。如果两个线程同属于一个进程，因为虚拟内存是共享等到，所以切换时虚拟内存的资源不动，只切换线程的私有数据、寄存器等不共享的数据。

如果锁住代码时间很短，则考虑使用自旋锁，因为上下文切换的时间可能比锁住代码的时间还长、

自旋锁通过CPU的CAS（Compare And Swap）函数在用户态实现加锁解锁，不会主动产生线程的上下文切换。加锁：查看锁状态，如果空闲则将锁设置为当前线程持有。CAS指令将这两个行为形成原子指令，设置成要么一次性执行两个，要么两个都不执行。自旋的线程永远不会放弃CPU

读写锁

读写锁适⽤于能明确区分读操作和写操作的场景，读写锁工作原理是，当写锁没有被线程持有时多个线程可以并发的持有读锁；当写锁被持有后，获取读锁的操作会被阻塞，其他写线程获取写锁的操作也会被阻塞。读写锁在读多写少的场景能够发挥出优势，也可以根据实现不同分为”读优先锁“和”写优先锁“

读优先锁工作方式：当有线程持有读锁后，其他线程获取写锁会被阻塞，并且在阻塞过程中后续来的读线程仍可以获取读锁；写优先锁工作方式：当有线程持有读锁后，写线程在获取写锁时会被阻塞，但是后续的读线程获取读锁时会失败

无论读优先或者写优先都可能导致对方出现饿死现象，所以有读写公平锁：比较简单的一种方式是，用队列把获取锁的线程排队，不管读进程还是写进程都按照先进先出的原则加锁即可，这样读线程仍可以并发，也不会出现饥饿现象

乐观锁和悲观锁

悲观锁认为多线程同时修改共享资源的概率较高容易出现冲突，其工作方式是：访问共享资源前都要先上锁。

乐观锁假定冲突概率很低，工作方式是：先修改共享资源，再验证这段时间有没有发生冲突，如果无冲突则操作完成，有冲突则放弃本次操作。乐观锁全程都没有加锁，所以也称无锁编程，比如共享文档。

乐观锁服务端验证是否发生冲突通常通过如下方案：先让用户编辑文档，浏览器下载文档时记录服务端的文档版本号，当用户提交修改时发给服务端的请求会带上原本的文档版本号，服务器收到后则与当前的比较，如果版本号一致则修改成功，否则提交失败。

总结

最常见是互斥锁，加锁失败则发生”线程切换“，发生两次上下文切换。

如果明确被锁住的代码执行时间很短，则考虑开销较小的自旋锁，自旋锁加锁失败时不会主动产生线程切换而是忙等待，如果被锁住的代码执行时间很短，忙等待的时间也会很短。

如果可以区分读操作和写操作的场景，读写锁会更合适，并根据具体情况决定偏袒读方还是写方，也有公平读写锁可以选择，其用队列来对请求锁的线程排队。

互斥锁、自旋锁、读写锁都属于悲观锁，悲观锁认为并发访问共享资源时冲突概率很高，所以访问前都要先加锁。如果冲突概率很低可以使用乐观锁，即访问共享资源时不用先加锁，修改完后再验证这段时间有没有发生冲突。

加锁的范围应该尽可能的小。

标签：信号量,互斥,线程,内核,进程,CPU
From： https://www.cnblogs.com/xccx-0824/p/17399433.html

四、进程与线程