🚧此页面处于维护期间，页面内容可能不准确 -This page is UNDER CONSTRUCTION-🚧

硬件结构

存储介质的层次关系

每个存储器只与相邻的存储器打交道，比如 CPU 想要访问内存中某个数据时，会先看看寄存器内部是否有该数据，若没有，再按 L1->L2->L3 的顺序依次递归查找，就像是倒置的双亲委派机制。

CPU 缓存

CPU Cache 一般分为三层，其中 L1、L2 是 CPU 核心独占的，L3 是各核心共享的。L1 中分为数据缓存和指令缓存。

对于数据缓存，我们在遍历数据的时候，应该按照内存布局的顺序操作，这是因为 CPU Cache 是根据 CPU Cache Line 批量操作数据的，所以顺序地操作连续内存数据时，性能能得到有效的提升；
对于指令缓存，有规律的条件分支语句能够让 CPU 的分支预测器发挥作用，进一步提高执行的效率；

Cache 对数据的组织方式有多种，下面以直接映射为例分析，直接映射通过将内存块的地址始终「映射」在一个 CPU Cache Line（缓存块，即 CPU Cache 一次能从内存中加载数据的多少）的地址，至于映射关系实现方式，则是使用「取模运算」，取模运算的结果就是内存块地址对应的 CPU Cache Line（缓存块）的地址。为了区分不同的映射到同一缓存块的内存块，CPU 使用组标记来标识。此外，缓存块中除了存储缓存内容之外，还会存储有效位（0、1）配合 MESI 缓存一致性协议。

CPU 从缓存块中读取数据时是按照字为单位读取，因此需要配合偏移量来定位数据，整体逻辑结构如下：

缓存一致性

CPU 在读写数据的时候，都是在 CPU Cache 读写数据的，原因是 Cache 离 CPU 很近，读写性能相比内存高出很多。对于 Cache 里没有缓存 CPU 所需要读取的数据的这种情况，CPU 则会从内存读取数据，并将数据缓存到 Cache 里面，最后 CPU 再从 Cache 读取数据。

在多级 CPU 缓存架构下，若采用的数据同步策略是写回策略，即只有在数据对应的（L1/L2 Cache 中）Cache Block 要被替换时，才能写回内存，若此时其他核心尝试读取同一变量的值，读到的将是旧值，缓存不一致性产生。

要解决这个问题，就要保证当一个核心对共享数据做修改时，其他核心能够感知此次修改，并且对于共享数据的操作对非操作核心而言，其顺序必须是串行化的。

总线嗅探

写传播的原则就是当某个 CPU 核心更新了 Cache 中的数据，要把该事件广播通知到其他核心。最常见实现的方式是总线嗅探（Bus Snooping）。

总线嗅探不能保证事务的串行化，并且总线嗅探对于总线的压力较大。

MESI 协议

MESI 协议其实是 4 个状态单词的开头字母缩写，分别是：

Modified，已修改
Exclusive，独占
Shared，共享
Invalidated，已失效

这四个状态来标记 Cache Line 四个不同的状态。

「已修改」状态就是我们前面提到的脏标记，代表该 Cache Block 上的数据已经被更新过，但是还没有写到内存里。而「已失效」状态，表示的是这个 Cache Block 里的数据已经失效了，不可以读取该状态的数据。

「独占」和「共享」状态都代表 Cache Block 里的数据是干净的，也就是说，这个时候 Cache Block 里的数据和内存里面的数据是一致的。「独占」和「共享」的差别在于，独占状态的时候，数据只存储在一个 CPU 核心的 Cache 里，而其他 CPU 核心的 Cache 没有该数据。这个时候，如果要向独占的 Cache 写数据，就可以直接自由地写入，而不需要通知其他 CPU 核心，因为只有你这有这个数据，就不存在缓存一致性的问题了，于是就可以随便操作该数据。在「独占」状态下的数据，如果有其他核心从内存读取了相同的数据到各自的 Cache ，那么这个时候，独占状态下的数据就会变成共享状态。

「共享」状态代表着相同的数据在多个 CPU 核心的 Cache 里都有，所以当我们要更新 Cache 里面的数据的时候，不能直接修改，而是要先向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后再更新当前 Cache 里面的数据。

伪共享问题

多个线程同时读取同一个缓存块（Cache Line）的不同变量时，导致 CPU Cache 失效的现象称为伪共享。

假设线程 A、B 已经将变量 A、B 读入了各自的缓存块中，由于 CPU 从内存读取的单位是缓存块的大小，A、B 两变量在内存中的位置是相邻的，所以在两个核心中均有 A、B 变量的本地缓存。

此时，若 A 核心想要修改 A 变量，由于 A 变量是共享状态，所以需要通知 B 核心，将 A 变量的状态设置为已失效（I），并修改 A 变量。

此后，若 B 核心想要修改变量 B，由于此时 B 内的缓存块是失效状态，且 A 内的 B 变量是已修改（M）状态，所以需要将 A 中的缓存块写回内存，B 核心再读取缓存块，做修改后将缓存块的状态设置为已修改（M）。

规避伪共享问题

OS 层面

Linux 内由一个宏定义，用于将变量在缓存块内对齐：__cacheline_aligned，可以达到以下效果：

内存管理

单片机上就只能同时运行一个程序，这是因为单片机不存在操作系统，也就是说没有操作系统来管理和映射逻辑地址和真实地址。

所以虚拟地址的引入就是为了使程序隔离运行，每个程序只能操作属于自己的那块内存，至于虚拟地址如何落到物理内存里，这个映射过程对程序是透明的。操作系统内部主要有两种维护虚拟地址和物理地址关系的模式：分页存储管理方式和分段存储管理方式。

分段存储管理方式

我们设计的程序其实天然就存在不同内存功能区域的划分，比如代码分段、数据分段、栈段、堆段等。

该机制下的虚拟地址由段号和段内偏移量组成，段表记录的是段的起始地址和段的长度。下图是该机制下的地址变换模式：

分段式的存储管理机制的缺点是：存在内存碎片，这里所说的内存碎片指的是外部内存碎片也就是说不是一块连续内存地址内的内存碎片，而是不同内存块之间的由于大小不能满足连续分配新内存块的区域，这部分区域就是外部内存碎片。

分页存储管理方式

分页的机制就是将整个虚拟内存和物理内存都分为一段段固定大小的区域，针对于虚拟内存侧，这个固定大小的区域称为页，对应的，物理地址侧的称为块。它们之间通过页表这个结构来完成映射。

当进程访问的虚拟内存在页表中查不到时，系统就会产生一个缺页异常。

分页的机制能够很好地解决分段式的外部碎片的问题，但随之带来的是内部碎片。当内存空间不够时，操作系统就会换出最近没有被使用的页到磁盘中，由于参与换出与换入的只是少量的页，所以内存交换的效率是比较高的。

下面的图片展示的是分页机制下物理地址与虚拟地址之间的映射关系，页表中包含的是虚拟的页号和对应的物理页号之间的关系，而虚拟地址包含的是页号和页内的偏移量。

多级页表

考虑到若只设置一级页表整个页表的体积将会非常庞大，于是引入了二级页表的概念。

如果某个一级页表的页表项没有被用到，就不会创建对应的二级页表。但是在未分级的页表机制中，为了保证覆盖全部的虚拟地址空间，需要创建大量的一级页表项来映射，成本较高。

TLB 快表

由程序的局部性原理可知，在一段时间内，执行的部分仅限于当前程序的某一部分，也就是说，访问的空间也只限于某个内存区域。

段页式内存管理

此方式下，虚拟地址由段号、段内页号和页内地址组成。

进程管理

进程

进程除了在 CPU 上运行时执行程序中的指令之外，在暂停时，也就是 CPU 组织进程切换时，当前进程必须要记录当前的运行状态信息，以备下次有机会时能够恢复运行。

在操作系统层面，一个进程有以下五个状态：

阻塞状态与其他状态之间的切换主要是因为当前线程因为请求某个事件而必须等待时，就像是 Java 中线程由RUNNING->WAITING状态的转换一样，一个线程退出阻塞状态后，由于不是立即就能获得时间片，所以是由阻塞->就绪状态，重新等待分时间片。

但是存在一种情况，进程长时间处于阻塞状态占用着宝贵的内存资源，这时可以利用换出技术将当前进程的物理内存空间换出到磁盘空间，节省内存使用，这时的进程状态处于挂起状态，挂起分为两种：

阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

进程的控制结构

PCB 是一个进程存在的唯一标志，PCB 中包含：

进程描述信息
进程控制和管理信息
资源分配清单
CPU 相关信息

PCB 通过链表的形式组织，一般把处于相同状态的进程的 PCB 链接在一起，组成各种队列。

进程的上下文切换

进程是由内核管理和调度的，所以进程的切换只发生在内核态。

进程的上下文切换包含了虚拟内存、栈等用户空间的资源，也包括了内核堆栈、寄存器等处于内核态的资源。通常，会把交换的信息保存在进程的 PCB 中。

发生场景

一个进程被分配的时间片到
进程在系统资源不足时会被挂起
进程通过 sleep 等函数主动让出运行权力时
发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序

线程

线程时 CPU 调度的基本单位，共享相同的地址空间。虽然线程之间共享进程的资源，但是每个线程都有独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

线程可以显著减低开销，主要体现在：

线程创建时间比进程快很多，主要就是因为线程之间对于资源的共享复用率比较高
用一个进程内的线程切换快，因为线程具有相同的地址空间，这就意味着同一个进程内的线程共享一个页表，线程切换也就不用切换页表
进程内的线程传递数据时不需要经过内核，数据传输效率更高

线程的上下文切换

若切换的线程同属于一个进程，则只需要切换线程有关的私有数据：寄存器、栈等
若切换的线程不属于同一进程，则线程的切换与进程切换一致

线程的实现

用户线程：多对一实现

用户线程操作系统不直接参与调度，用户线程的切换是由线程库函数来完成的，不涉及到用户态与内核态的切换。但也因为操作系统不直接参与调度，所以如果一个线程发起了系统调用而阻塞，该进程包含的其他用户线程均不能执行。而且除非一个用户线程主动交出 CPU 使用权，其他线程无法运行，因为用户态线程无法打断运行中的线程。

内核线程：一对一实现，即一个用户线程对应一个内核线程

由于线程的 TCB 是存储在内核中的，所以不会出现因阻塞调用而导致影响其他线程运行的情况，但由于线程的终止、创建等操作都是由系统调用来完成，开销会比较大。

轻量级进程：多对多实现

一个进程可以有多个 LWP（Light-weight Process），一个 LWP 由一个内核线程支持，LWP 是由内核管理并像普通进程一样调度。

LWP与普通进程的区别也在于它只有一个最小的执行上下文和调度程序所需的统计信息。

调度

这里的调度一般指的是只有主线程的进程的调度。

调度时机

以下状态的变化都会触发操作系统的调度：

从就绪态 -> 运行态：当进程被创建时，会进入到就绪队列，操作系统会从就绪队列选择一个进程运行；
从运行态 -> 阻塞态：当进程发生 I/O 事件而阻塞时，操作系统必须选择另外一个进程运行；
从运行态 -> 结束态：当进程退出结束后，操作系统得从就绪队列选择另外一个进程运行；

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

非抢占式调度算法
抢占式调度算法

调度原则

从 CPU 利用率、系统吞吐量、周转时间、等待时间、响应时间等五个方面来考虑。

调度算法

以下算法均基于单核环境

先来先服务算法

最简单的一个调度算法，就是非抢占式的先来先服务（First Come First Serve, FCFS）算法了。

FCFS 对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。

最短作业优先调度算法

最短作业优先（Shortest Job First, SJF）调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

这显然对长作业不利，很容易造成一种极端现象。

比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。

高响应比优先调度算法

高响应比优先（Highest Response Ratio Next, HRRN）调度算法主要是权衡了短作业和长作业。

每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行，「响应比优先级」的计算公式：

时间片轮转调度算法

每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。

如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配给另外一个进程；
如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

另外，时间片的长度就是一个很关键的点：

如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；
如果设得太长又可能引起对短作业进程的响应时间变长。

一般来说，时间片设为 20ms~50ms 通常是一个比较合理的折中值。

最高优先级调度算法

对于多用户计算机系统而言，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法。

进程的优先级可以分为，静态优先级和动态优先级：

静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

该算法也有两种处理优先级高的方法，非抢占式和抢占式：

非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

但是依然有缺点，可能会导致低优先级的进程永远不会运行。

多级反馈队列调度算法

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

顾名思义：

「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；

设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；

可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也变更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。下图是以银行办理业务的场景来类比的多级反馈队列调度算法：

进程间通信方式

管道

分为匿名管道和命名管道。

管道其实就是内核里面的一串缓存，通过fork子进程的方式实现不同进程之间的通信。

对于匿名管道，通信的范围是同一父进程创建的子进程之间；对于命名管道，支持不同进程之间通信。

消息队列

不同于管道内部的无格式的字节流数据，消息队列在内核中传递的是消息体。

消息队列的缺点主要是不及时并且也存在内核态和用户态之间的数据拷贝开销。

共享内存

共享内存就是拿出一块虚拟空间来，映射到相同的物理内存内。

信号量

信号量的提出是为了解决共享内存中对于共享资源的并发操作的问题，为了防止多个进程竞争共享资源，利用信号量维护了一个整型的计数器，控制信号量有两种方式：

一个是 P 操作（加锁），这个操作会把信号量减去 1，相减后如果信号量 < 0，则表明资源已被占用，进程需阻塞等待；相减后如果信号量 >= 0，则表明还有资源可使用，进程可正常继续执行。
另一个是 V 操作（解锁），这个操作会把信号量加上 1，相加后如果信号量 <= 0，则表明当前有阻塞中的进程，于是会将该进程唤醒运行；相加后如果信号量 > 0，则表明当前没有阻塞中的进程；

若将信号量初始为 0，说明是同步信号量，可以用于实现多进程同步。

信号

信号是进程间通信的唯一的异步通信机制，一旦有信号产生，我们可以：

执行默认操作。Linux 对每种信号都规定了默认操作，例如，上面列表中的 SIGTERM 信号，就是终止进程的意思。
捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。
忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

Socket

适用于跨网络与不同主机之间的通信。

Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式。

多线程冲突

举一个简单的例子，多线程循环更新i变量 20000 次，若不对此共享变量做任何处理的话，最后得到的值将会是多样的（也有可能是 20000）。发生这种现象的主要原因是对变量i的操作实际上是三条指令共同作用的结果，先取出后修改最后写回，所以，由于操作系统对于线程的调度，不同线程内指令的执行顺序是不可控的。

上面展示的情况称为竞争条件（race condition），当多线程相互竞争操作共享变量时，由于运气不好，即在执行过程中发生了上下文切换，我们得到了错误的结果，事实上，每次运行都可能得到不同的结果，因此输出的结果存在不确定性（indeterminate）。

由于多线程执行操作共享变量的这段代码可能会导致竞争状态，因此我们将此段代码称为临界区（critical section），它是访问共享资源的代码片段，一定不能给多线程同时执行。

我们希望这段代码是互斥（mutualexclusion）的，也就说保证一个线程在临界区执行时，其他线程应该被阻止进入临界区，说白了，就是这段代码执行过程中，最多只能出现一个线程。

我们希望对共享资源存在争抢的线程之间能够相互独立，但有时候又希望多个线程之间能够相互合作，共同完成任务。

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

下面简要介绍两种实现同步与互斥的机制：锁与信号量

锁

任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可进入临界区；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。

忙等待锁（自旋锁）：线程阻塞等待，直到获取到锁
无等待锁

信号量

之前在进程间通信部分也简单聊过这个工具，通过 P、V 这两个原子的系统操作来操作这个信号量。

利用 PV 操作实现互斥

我们将信号量的初始值定义为 1，若信号量变为 0，代表有一个线程进入了临界区，若信号量值为 -1，表示有一个线程正处于临界区，存在另一线程等待进入

利用 PV 操作实现同步操作

我们将信号量的初始值定义为 0,同步的具体过程如下：

如果进程 B 比进程 A 先执行了，那么执行到 P 操作时，由于信号量初始值为 0，故信号量会变为 -1，表示进程 A 还没生产数据，于是进程 B 就阻塞等待；
接着，当进程 A 生产完数据后，执行了 V 操作，就会使得信号量变为 0，于是就会唤醒阻塞在 P 操作的进程 B；
最后，进程 B 被唤醒后，意味着进程 A 已经生产了数据，于是进程 B 就可以正常读取数据了。

生产者-消费者问题

同一时间只能有一人访问共享数据区,实现互斥,但是当缓冲区为空时,消费者必须等待生产者产生数据,缓冲区为满时,生产者必须等待消费者消费数据,也就是要实现同步.

互斥信号量 mutex：用于互斥访问缓冲区，初始化值为 1；
资源信号量 fullBuffers：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）；
资源信号量 emptyBuffers：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n （缓冲区大小）；

#define N 100
semaphore mutex = 1;//互斥信号量，用于临界区的互斥访问
semaphore emptyBuffers = N;//表示缓冲区「空槽」的个数
semaphore fullBuffers = 0;//表示缓冲区「满槽」的个数
//生产者线程函数
void producer()
{
    while(TRUE){
        P(emptyBuffers);// 将空槽的个数－ 1
        P(mutex);//进入临界区
        将生成的数据放到缓冲区中；
        V(mutex);//离开临界区
        V(fullBuffers);//将满槽的个数+ 1
    }
}
//消费者线程函数
void consumer()
{
while(TRUE)
    {
        P(fullBuffers);// 将满槽的个数－ 1
        P(mutex);//进入临界区
        从缓冲区里读取数据；
        V(mutex);//离开临界区
        V(emptyBuffers);//将空槽的个数 + 1
    }
}

哲学家就餐问题

N个哲学家,N-1支筷子,同时拿到左右两边筷子的才能进餐,用餐完毕放下两边筷子.

解决方案 1:偶数编号的哲学家「先拿左边的叉子后拿右边的叉子」，奇数编号的哲学家「先拿右边的叉子后拿左边的叉子」。

解决方案 2:利用数组记录哲学家的状态,分别是进餐 \ 思考 \ 饥饿(试图拿取叉子),一个哲学家只有左右两侧的邻居都没有进餐时才能尝试拿去餐具,才可以进入进餐状态:

#define N 5//哲学家个数
#define LEFT （i + N1）N//的左边邻居编号
#define RIGHT （i + 1) % N//的右边邻居编号

#define THINKING 0//思考状态
#define HUNGRY//饥饿状态
#define EATING//进餐状态

int state[N];//数组记录每个哲学家的状态

semaphore s[5];//每个哲学家一个信号量，初值
semaphore mutex;//互斥信号量，初值为 1
void test（int i）//为哲学家编号 0-4
{
    //如果i号的左边右边哲学家都不是进餐状态，把讠号哲学家标记为进餐状态
    if(state[i] == HUNGRY &&state[LEFT] != EATING &&state[RIGHT] != EATING )
    {
        state[i]=EATING //两把叉子到手，进餐状态
        v(s[il);/通知第讠哲学家可以进餐了
    }
//功能：要么拿到两把叉子，要么被阻塞起来
void take_forks（inti）//i为哲学家编号0-4
{
    P(mutex);//进入临界区
    state[i] = HUNGRY;//标记哲学家处于饥饿状态
    test(i);//尝试获取 2 支叉子
    V(mutex);//离开临界区
    P(s[il);//没有叉子则阻塞，有叉子则继续正常执行
}
//功能：把两把叉子放回原处，并在需要的时候，去唤醒左邻右舍
void put_forks（inti）//讠为哲学家编号0-4
{
    P(mutex);//进入临界区
    state[i］=THINKING;//吃完饭了，交出叉子，标记思考状态
    test(LEFT);//检查左边的左邻右舍是否在进餐，没则唤醒
    test(RIGHT);//检查右边的左邻右舍是否在进餐，没则唤醒
    V( mutex);离开临界区
}
//哲学家主代码
void smart_person(int i）//讠为哲学家编号0-4
{
    while(TRUE)
    think();//思考
    take_forks(i)；//准备拿去叉子吃饭eat();/就餐
    put_forks(i);/吃完放回叉子
}

读者-写者问题

信号量 wMutex：控制写操作的互斥信号量，初始值为 1 ；
信号量 rCountMutex：控制对 rCount 读者计数器的互斥修改，初始值为 1；
读者计数 rCount：正在进行读操作的读者个数，初始化为 0；

semaphore wMutex;
semaphore rCountMutex;
int count = 0;

void writer(){
    while (TRUE){
        P(wMutex);
        write();
        V(wMutex);
    }
}

void reader(){
    while (TRUE){
        P(rCountMutex);
        if (count == 0){
            P(wMutex);
        }
        rCount++;
        V(rCountMutex);

        read();

        P(rCountMutex);
        rCount--;
        if (count == 0){
            V(wMutex);
        }
        V(rCountMutex);
    }
}

进程能创建的最大线程数

这个问题需要从不同角度来考虑，在 Linux 操作系统中，虚拟地址空间内部又被分为内核空间和用户空间，在不同位数的系统中，这两者的具体大小也不同，具体如下图所示：

可见，在 32 位系统中，若对于每个线程分配的栈空间为 10M，那么一个进程最多只能分配 300 个左右的线程。但是在 64 位系统中，能创建的线程数是无限的，这时就要通过系统参数来做进一步限制，比如_**/proc/sys/kernel/threads-max**_这个参数。

线程崩溃问题

在 C++中，进程会随着内部线程的崩溃一并崩溃。但是在 Java 中，进程不会随着内部线程一并崩溃。下面简述一下原因。

首先，我们知道进程内的线程是共享了一片地址空间的，所以当某个线程发生了非法的内存访问时，操作系统处于安全性的考虑，决定让整个进程崩溃，内部的正常的线程此时也会被终止。线程崩溃后，会向进程发送信号kill。

CPU 执行正常的进程指令
调用 kill 系统调用向进程发送信号
进程收到操作系统发的信号，CPU 暂停当前程序运行，并将控制权转交给操作系统
调用 kill 系统调用向进程发送信号（假设为 11，即 SIGSEGV，一般非法访问内存报的都是这个错误）
操作系统根据情况执行相应的信号处理程序（函数），一般执行完信号处理程序逻辑后会让进程退出

但在 Java 中，处于对资源的利用率和工程的健壮性等方面的考虑，JVM 不会直接让整个进程终止，Java 先择自行实现信号处理函数，拦截了有关的信号。

在信号处理函数中对（StackoverflowError 和 NPE）做了额外的处理以让 JVM 不崩溃，另一方面也可以看出如果 JVM 不对信号做额外的处理，最后会自己退出并产生 crash 文件 hs_err_pid_xxx.log（可以通过 -XX:ErrorFile=/var/log/hs_err.log 这样的方式指定），这个文件记录了虚拟机崩溃的重要原因。

文件系统

文件系统是负责管理持久数据的子系统，在 Linux 系统中有“一切皆文件”的概念。

文件的使用

要使用一个文件，就要调用系统提供的相应函数，比如下面代码块中展示了系统向上提供的三个操作文件的系统调用：

fd = open(name, flag); # 打开文件
...
write(fd,...);         # 写数据
...
close(fd);             # 关闭文件

文件打开后，操作系统会追踪一个文件的情况，每个进程维护了一张** 打开文件表，里面的每一项维护了文件指针、文件打开计数器**、文件磁盘位置等信息。

文件的存储

连续空间存储

顾名思义，文件就存储在连续的物理空间中，目录项中需要存储起始位置和块长度。

缺点：磁盘空间碎片、文件长度不易拓展

非连续空间存储

链式

链式存储分为隐式和显式链表存储，区别在于隐式存储只需要存储开始结点指针和结尾结点指针，下图展示的是隐式链接存储：

显式链接就是将所有用于连接文件块的指针抽取到一张链接表中，统一管理。不像隐式链接访问文件块需要通过指针顺序访问文件，由于显式链接用于存储指针的文件分配表（FAT）是位于内存中的，所以即使也需要通过顺序遍历来查找数据，也是要比隐式存储快很多的。下图是 FAT 的示意图：

索引

为了更好的支持直接访问，决定维护一个索引列表，索引的实现是为每个文件创建一个「索引数据块」，里面存放的是指向文件数据块的指针列表，目录项需要包含指向索引数据块的指针。

空闲区间管理

空闲表法

维护每个空间区间的首个空闲块和区间总共的空闲块数。

如果存储空间中有着大量的小的空闲区，则空闲表变得很大，这样查询效率会很低。另外，这种分配技术适用于建立连续文件。

空闲链表法

我们也可以使用「链表」的方式来管理空闲空间，每一个空闲块里有一个指针指向下一个空闲块，这样也能很方便的找到空闲块并管理起来。

位图法

位图是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。

文件共享

在早期的操作系统中，多个用户想要共享一个文件只能通过复制的形式来完成，下面介绍两种方式来实现文件复用。

硬链接：利用索引节点解决文件共享问题

即在文件目录项中存储的不是文件的物理地址，而是指向文件地址的索引结点的地址，索引节点中还维护了链接的计数，也就是同一个文件被引用的次数，只有删除文件的所有硬链接以及源文件时，系统才会彻底删除该索引。

软链接：利用符号链接实现文件共享

允许一个文件或子目录拥有多个父目录，但其中只有一个作为主父目录。

设备管理

设备控制器

为了屏蔽不同设备之间的差异，每个设备都有一个设备控制器，由于它们很清楚设备的运转机理，所以 CPU 通过它们来与设备打交道。

为了存放与 CPU 交换的信息，设备控制器内部有三种寄存器设备：

数据寄存器，CPU 向 I/O 设备写入需要传输的数据，比如要打印的内容是「Hello」，CPU 就要先发送一个 H 字符给到对应的 I/O 设备。
命令寄存器，CPU 发送一个命令，告诉 I/O 设备，要进行输入/输出操作，于是就会交给 I/O 设备去工作，任务完成后，会把状态寄存器里面的状态标记为完成。
状态寄存器，目的是告诉 CPU ，现在已经在工作或工作已经完成，如果已经在工作状态，CPU 再发送数据或者命令过来，都是没有用的，直到前面的工作已经完成，状态寄存标记成已完成，CPU 才能发送下一个字符和命令。

输入输出设备整体上分为块设备和字符设备两类，它们因为传输的数据量而不同。块设备的传输数据量通常会非常大，所以 CPU 为块设备设置了一个数据缓冲区，用于暂存数据。

I/O 控制方式

前面提到，状态寄存器用于存储工作的状态，那么 CPU 该如何获取，或者说该以什么方式来获取工作的状态呢？

轮询等待与中断

这两种方式都不太好，前者会让 CPU 处于忙等的状态，后者由于中断处理程序执行需要耗费一定时间，对于数据频繁读写的磁盘不友好。

DMA 方式

使得 I/O 内的寄存器的内容直接与内存做交换，跳过 CPU 的干涉，要实现该功能，需要 DMA 控制器的支持。

DMA 工作方式如下：

CPU 需对 DMA 控制器下发指令，告诉它想读取多少数据，读完的数据放在内存的某个地方就可以了；
接下来，DMA 控制器会向磁盘控制器发出指令，通知它从磁盘读数据到其内部的缓冲区中，接着磁盘控制器将缓冲区的数据传输到内存；
当磁盘控制器把数据传输到内存的操作完成后，磁盘控制器在总线上发出一个确认成功的信号到 DMA 控制器；
DMA 控制器收到信号后，DMA 控制器发中断通知 CPU 指令完成，CPU 就可以直接用内存里面现成的数据了；

仅仅在传送开始和结束时需要 CPU 干预。

设备驱动程序

每种设备对于控制器的寄存器的使用方式是不同的，为了屏蔽设备控制器的差异，引入了设备驱动程序。

设备控制器不属于操作系统范畴，它是属于硬件，而设备驱动程序属于操作系统的一部分，操作系统的内核代码可以像本地调用代码一样使用设备驱动程序的接口，而设备驱动程序是面向设备控制器的代码，它发出操控设备控制器的指令后，才可以操作设备控制器。

前面有提到，若设备完成了工作，会向操作系统发送通知，而中断处理程序就是用于处理中断的程序。

中断程序的工作流程如下：

在 I/O 时，设备控制器如果已经准备好数据，则会通过中断控制器向 CPU 发送中断请求；
保护被中断进程的 CPU 上下文；
转入相应的设备中断处理函数；
进行中断处理；
恢复被中断进程的上下文；

通用块层

前面提到，I/O 设备主要分为两种，其中的一种是块设备，它们以数据缓冲区来完成数据传输，但是不同的块设备之间的性能差异是较大的，所以 Linux 通过通用块层来屏蔽差异。

文件系统层，包括虚拟文件系统和其他文件系统的具体实现，它向上为应用程序统一提供了标准的文件访问接口，向下会通过通用块层来存储和管理磁盘数据。
通用块层，包括块设备的 I/O 队列和 I/O 调度器，它会对文件系统的 I/O 请求进行排队，再通过 I/O 调度器，选择一个 I/O 发给下一层的设备层。
设备层，包括硬件设备、设备控制器和驱动程序，负责最终物理设备的 I/O 操作。

网络系统

DMA技术

先来看看中断式 I/O 的整体流程：

read(file, tmp_buf, len);
write(socket, tmp_buf, len);

也就是说，在 CPU 把数据从缓冲区读入自己的寄存器时，CPU 无法执行其他任务。而 DMA(Direct Memory Access)技术的提出将数据的搬运工作全部交给了 DMA 控制器，CPU 不再参与任何数据搬运的相关工作。

在传统的文件传输方式下，会发生多次用户态和内核态之间的转换，下面是网络传输的信息如何进入到进程中的示意图：

想要提高文件传输的效率，要从**减少用户态和内核态的上下文切换和减少数据搬运次数 **出发。

为什么会发生用户态和内核态的上下文切换，是因为用户态没有权利直接调用网卡或磁盘，想要调用他们，就必须通过调用系统函数的方式来实现，所以减少用户态和内核态的上下文切换的根本是减少系统调用。

至于数据拷贝次数的问题，我们的数据流转方向是：磁盘->内核缓冲区->用户缓冲区，其实第一次的流转是没有必要的，因为不会对数据再做加工处理。

接下来，我们看看零拷贝技术是如何解决上面提出的问题的。

零拷贝技术

著名的 Kafka 和 Nginx 就是基于零拷贝技术实现的高吞吐量。

mmap+write

mmap函数会将内核中的缓冲区直接映射到用户的缓冲区，也就是将原本的 CPU 拷贝的步骤删去。

应用进程调用了 mmap() 后，DMA 会把磁盘的数据拷贝到内核的缓冲区里。接着，应用进程跟操作系统内核「共享」这个缓冲区；

这种方式在数据写回时，仍是采用的write函数，还是存在无效的数据拷贝。

sendfile

ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);

前两个参数是目标端和源端的文件描述符，后面两个参数是期待读取的偏移量和实际读取的数据长度。

该系统调用可以直接把内核缓冲区里的数据拷贝到 socket 缓冲区里，不再拷贝到用户态，这样就只有 2 次上下文切换，和 3 次数据拷贝。

通过 DMA 将磁盘上的数据拷贝到内核缓冲区里；
缓冲区描述符和数据长度传到 socket 缓冲区，这样网卡的 SG-DMA 控制器就可以直接将内核缓存中的数据拷贝到网卡的缓冲区里，此过程不需要将数据从操作系统内核缓冲区拷贝到 socket 缓冲区中，这样就减少了一次数据拷贝；

所以，在上面展示的零拷贝模型中，就不涉及到 CPU 对于数据的搬运，自然就减少了两次数据拷贝过程；

关于大文件传输的思考

如果采用传统的阻塞式 I/O 实现，用户进程会长时间阻塞等待，我们可以考虑采用异步 I/O 来解决这个问题。

前半部分，内核向磁盘发起读请求，但是可以不等待数据就位就可以返回，于是进程此时可以处理其他任务；
后半部分，当内核将磁盘中的数据拷贝到进程缓冲区后，进程将接收到内核的通知，再去处理数据；

I/O 多路复用技术

基本 socket 模型

之前在讲进程间通信的时候，提到过如果涉及到跨主机或网段之间的进程，可以采用 socket 来做通信方式。

在发起一次通信前，服务端需要根据 IP 协议和 TCP 协议建立一个 socket，接着将该 socket 绑定到指定的 IP 和端口上。

完成上面的准备工作后，可以调用listen函数来监听，调用accept函数从内核获取客户端连接，对应的，客户端调用connect函数发起 TCP 连接，在三次握手期间，服务端内部维护了两个队列，分别是 TCP 半连接队列和 TCP 全连接队列。前面说到的accept函数就会从全连接队列中选取一个返回客户端。

之后，通过调用 read() 和 write() 函数来读写数据。

上面的通信模型是最基本的一对一的通信，接下来我们来看看能通过什么方式在服务端资源有限的情况下服务更多的客户端。

多线程模型

服务器的主进程负责监听客户的连接，一旦与客户端连接完成，accept() 函数就会返回一个「已连接 Socket」，这时就通过 fork() 函数创建一个子进程，实际上就把父进程所有相关的东西都复制一份，包括文件描述符、内存地址空间、程序计数器、执行的代码等。

多线程模型

上面的多进程模型涉及到笨重的进程切换，由于子是复用的父的资源（就绪 socket）所以可以采用多线程的方式来处理客户端请求。还可以使用线程池技术来复用已经创建的线程资源。

I/O 多路复用

之前的 I/O 模型那块也讲过相关知识，这里再做一下复习。

I/O 多路复用的核心思想就是用一个进程来维护多个 socket，像常见的 select、poll、epoll 就是内核向外暴露的多路复用的系统 API，下面重点说一下 epoll。

如下的代码中，先用e poll_create 创建一个 epol l对象 epfd，再通过 epoll_ctl 将需要监视的 socket 添加到epfd中，最后调用 epoll_wait 等待数据。

int s = socket(AF_INET, SOCK_STREAM, 0);
bind(s, ...);
listen(s, ...)

int epfd = epoll_create(...);
epoll_ctl(epfd, ...); //将所有需要监听的socket添加到epfd中

while(1) {
    int n = epoll_wait(...);
    for(接收到数据的socket){
        //处理
    }
}

epoll 在内核维护了一颗用于存储 FD 的红黑树，需要的时候只需要传入一个待检测的 socket，在 O(logn)内便能查找到数据，相对高效。

epoll 使用事件驱动的机制，内核里维护了一个链表来记录就绪事件，当某个 socket 有事件发生时，通过回调函数内核会将其加入到这个就绪事件列表中，当用户调用 epoll_wait() 函数时，只会返回有事件发生的文件描述符的个数，不需要像 select/poll 那样轮询扫描整个 socket 集合，大大提高了检测的效率。

除了返回就绪的文件描述符数量外，epoll_wait 还会填充一个由用户提供的 struct epoll_event 类型的数组。这个数组实际上就是就绪的文件描述符的集合。

边缘触发和水平触发

LevelTriggered：简称LT，也叫做水平触发。只要某个FD中有数据可读，每次调用epoll_wait都会得到通知。若原链表中还有FD数据未读取完，会再次添加到链表。
EdgeTriggered：简称ET，也叫做边沿触发。只有在某个FD有状态变化时，调用epoll_wait才会被通知。当FD从链表中移除后，不管是否读取完毕都不再添加回链表。

select/poll 只有水平触发模式，epoll 默认的触发模式是水平触发，但是可以根据应用场景设置为边缘触发模式。