操作系统面试题

2022-02-05 约 20222 字预计阅读 41 分钟

硬件结构

CPU是如何执行程序的？

冯洛伊曼模型

定义了计算机的基本结构为5个部分，分别是：运算器、控制器、存储器、输入设备和输出设备。

指令周期

CPU的工作方式就是一个指令周期接着一个周期的方式，而一个指令周期包括如下四个阶段

CPU 通过程序计数器读取对应内存地址的指令，这个部分称为 Fetch（取得指令）；

CPU 对指令进行解码，这个部分称为 Decode（指令译码）；

CPU 执行指令，这个部分称为 Execution（执行指令）；

CPU 将计算结果存回寄存器或者将寄存器的值存入内存，这个部分称为 Store（数据回写）；

存储器的层次结构

存储器通常可以分为四个层次，分别为：寄存器、L1/L2/L3 Cache、内存、硬盘。

CPU缓存一致性

CPU Cache的数据写入

CPU将数据写入CPU Cache中后，会导致Cache中数据与内存中不一致，什么时机将缓存中的数据写入到内存呢？

写直达(Write Throush)

把数据同时写入到内存和Cache中，这样的写操作会花费大量的时间。

写回(Write Back)

发生写操作时，如果数据已经在CPU Cache里面，则把数据直接更新到CPU Cache中，同时将该数据标记为脏。
写操作时，如果这个Cache Block中的数据是别的内存地址的数据，就需要判断是否被标记为脏：
1. 如果标记为脏，就需要将这个Cache Block中的数据写回内存，然后将要写入的数据先从内存读取到Cache Block中，然后再写入并标记为脏。
2. 如果没有标记，则同理先从内存中读取要写入的数据到Cache Block中，再写入并标记。

缓存一致性问题

现在由于都是多核CPU，L1/L2Cache是多核心各自独占的，那么就会带来缓存一致性问题。例如A、B两个核心都操作变量i，A核心将变量i修改为1，这个更新还没同步到内存中，那么B核心就会读取到不一致的数据。要同步不同核心之间的缓存数据，就需要做到以下两点：

某个CPU的Cache数更新时，必须传播到其他核心，称之为写传播

CPU对数据的操作顺序，必须在其他核心看起来一致。称之为事务的串行化。

基于总线嗅探的MESI协议

该协议能够满足上面的两点，保障缓存一致性。MESI协议是以下四种Cache Line状态的缩写：

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

已修改(即前面说的标记为脏)和独占状态的Cache Line更新不需要通过总线进行广播。共享状态下的写操作，则需要先向其他核心广播一个请求，将其他核心的缓存数据变为已失效，再进行写操作。

伪共享问题

由于CPU从内存中将数据读取到Cache中时，采用一块一块的方式进行读取，这样的块数据称之为Cache Line。当多个核心同时读写同一个Cache Line中的不同变量的时候。

例如，1核心只读写A变量，2核心只读写B变量，A、B变量属于同一个Cache Line，1核心修改A变量会导致2核心的Cache Line状态变为失效，之后2核心修改B变量时，1核心需要先把Cache Line写入内存，然后状态变为失效，然后2核心再读取数据到Cache中，进行修改。

这样会导致同属于一个Cache Line的数据任意修改都会相互影响，称之为伪共享问题。

避免伪共享问题的思路就是空间换时间：对于同一个Cache Line的热点数据，可以使不同变量在Cache Line中对齐，从而防止伪共享问题发生。使用字节填充的方式或者通过Linux中__cacheline_aligned_in_smp 宏定义实现Cache Line大小字节对齐方式来解决伪共享问题。

软中断

中断是什么？

中断是系统响应硬件设备请求的一种机制，操作系统接收到了中断请求，会打断其他进程的运行。所以中断处理程序要尽可能快的执行完，减少对正常进程运行调度的影响。而且中断处理程序在响应中断时，可能会临时关闭中断，这意味着，如果当前中断处理程序没有执行完之前，系统中其他的中断请求都无法被响应，也就说中断有可能会丢失。

什么是软中断？

Linux系统为了解决中断处理程序执行过长和中断丢失的问题，将中断分为了两个阶段：

上半部直接处理硬件请求，也称为硬中断，一般会暂时关闭中断请求，主要负责处理跟硬件紧密相关或者时间敏感的事情。

下半部由内核触发，也称为软中断，主要是负责上半部未完成的工作，通常都是耗时比较长的事情，特点是延迟执行。

内存管理

为什么要有虚拟内存？

虚拟内存

如果CPU直接操作内存的物力地址，那么要在内存中同时运行两个程序是不可能的，因为可能出现第一个程序擦除第二个程序存放在内存中内容的情况。操作系统引入了虚拟内存，为每一个进程分配一套独立的虚拟地址，将进程与物理内存隔离开。进程持有的虚拟地址会通过CPU中的内存管理单元(MMU)的映射关系，转换变成物理地址，然后再通过物理地址访问内存。

虚拟内存的作用？

虚拟内存可以使得进程的运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域。

由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。

页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性。

内存分段

操作系统如何管理虚拟地址与物理地址之间的关系？

主要有两种方式，分别为内存分段和内存分页。

程序由若干逻辑分段组成，例如代码分段、数据分段、栈段、堆段等。不同的段有不同的属性，所以采用分段的形式将这些段分离出来。虚拟地址通过段表与物理地址进行映射。分段机制下虚拟地址由段选择因子和段内偏移量两部分组成。

段选择因子就保存在段寄存器里面。段选择因子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。

虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。

内存分段的不足之处？

内存分段容易产生内存碎片并且内存交换的效率低下。

内存分段由于是根据需求分配内存，因此不会产生内部内存碎片。但是由于每个段的长度不固定，所以多个段未必能恰好使用所有的内存空间，会产生了多个不连续的小物理内存，导致新的程序无法被装载，所以会出现外部内存碎片的问题。

解决的办法就是内存交换？

即将程序占用的内存写到硬盘，然后再重新读回内存。Linux的Swap空间就是银盘划分出来用于内存与硬盘的空间交换的。

但是由于需要将一大段内存写入到硬盘中，因此会出现内存交换效率低下的问题。

内存分页

分段的好处就是能产生连续的内存空间，但是会出现外部内存碎片和内存交换效率低下的问题。

内存分页则解决了这些问题，分页将整个虚拟和物理内存空间切成一段段固定尺寸的大小， 我们称之为页。虚拟地址和物理地址则通过页表来进行映射。

内存分页如何解决内存分段的缺陷的？

由于采用了分页的方式，页与页之间是紧密排列的，所以不会有外部碎片。 但是可能会出现内存碎片的情况。

如果内存空间不够，操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉，也就是暂时写在硬盘上，称为换出（Swap Out）。一旦需要的时候，再加载进来，称为换入（Swap In）。所以，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高。

在分页机制下，虚拟地址分为页号和页内偏移。页号作为页表的索引，页表 包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址。

由于每个进程都需要维护一个页表，因此页表也需要占据大量的空间，因此有了多级页表。

多级页表

为什么多级页表更加节约空间呢？每增加一级页表维护，应该需要增加空间的消耗才对？

页表承担的责任是将虚拟内存地址映射到物理内存地址，因此页表一定要全部覆盖虚拟地址空间。如果是一级页表，那么一级页表则承担覆盖全部虚拟地址空间的责任，一页都不能缺少。如果采用多级页表，则最高一级的页表覆盖所有的虚拟内存地址，只需要少量内存空间，因为局部性原理，一级页表可以被操作系统换出到硬盘，不用占据物理内存。

TLB

多级页表解决了空间的问题，但是降低了虚拟内存地址到物理内存地址的转换速率，因此有了TLB(页表缓存) ，将最常访问的页表项存储到其中，CPU寻址则会先查询TLB，再查询常规页表。

段页式内存管理

将内存分页管理和内存分段管理组合起来，就称之为段页式内存管理。

先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制，接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页。这样地址结构就由段号、段内页号和页内偏移 三部分组成。

内存满了，会发生什么？

内存分配过程

应用程序通过malloc函数申请内存的时候，实际上申请的是虚拟内存，并不会分配物理内存。当CPU读写了这一块虚拟内存，发现虚拟内存并没有映射到物理内存中，CPU就会产生缺页中断， 进程从用户态切换到内核态，并将缺页中断交给内核的缺页中断函数 处理。

缺页中断函数会看是否有空闲的物理内存，如果有就直接进行分配。
如果没有，内核就会开发进行内存回收 工作，内存回收工作主要是两种：直接内存回收和后台内存回收。

后台内存回收(kswapd)：在物理内存紧张的时候，会唤醒 kswapd 内核线程来回收内存，这个回收内存的过程异步的，不会阻塞进程的执行。

直接内存回收：如果后台异步回收跟不上进程内存申请的速度，就会开始直接回收，这个回收内存的过程是同步的，会阻塞进程的执行。

如果直接内存回收后，空闲的物理内存仍然无法满足此次物理内存的申请，那么内核就会放最后的大招了 ——触发 OOM （Out of Memory）机制。OOM Killer 机制会根据算法选择一个占用物理内存较高的进程，然后将其杀死，以便释放内存资源，如果物理内存依然不足，OOM Killer 会继续杀死占用物理内存较高的进程，直到释放足够的内存位置。OOM killer 就会根据每个进程的内存占用情况和 oom_score_adj 的值进行打分，得分最高的进程就会被首先杀掉。 我们可以通过调整oom_score_adj的值来降低被OOM killer杀死的概率。

可被回收的内存类型有文件页和匿名页：

文件页的回收：对于干净页是直接释放内存，这个操作不会影响性能，而对于脏页会先写回到磁盘再释放内存，这个操作会发生磁盘 I/O 的，这个操作是会影响系统性能的。

匿名页的回收：如果开启了 Swap 机制，那么 Swap 机制会将不常访问的匿名页换出到磁盘中，下次访问时，再从磁盘换入到内存中，这个操作是会影响系统性能的。

文件页和匿名页的回收都是基于 LRU 算法，也就是优先回收不常访问的内存。回收内存的操作基本都会发生磁盘 I/O 的，如果回收内存的操作很频繁，意味着磁盘 I/O 次数会很多，这个过程势必会影响系统的性能。

针对内存回收导致的性能影响，常见的解决方案是：

设置 /proc/sys/vm/swappiness，调整文件页和匿名页的回收倾向，尽量倾向于回收文件页；

设置 /proc/sys/vm/min_free_kbytes，调整 kswapd 内核线程异步回收内存的时机；

设置 /proc/sys/vm/zone_reclaim_mode，调整 NUMA 架构下内存回收策略，建议设置为 0，这样在回收本地内存之前，会在其他 Node 寻找空闲内存，从而避免在系统还有很多空闲内存的情况下，因本地 Node 的本地内存不足，发生频繁直接内存回收导致性能下降的问题；

在4G物理内存的机器上，申请8G内存会怎么样？

32位和64位操作系统的虚拟地址空间大小是不同的，Linux操作系统中，虚拟地址空间又分为了内核空间和用户空间 两部分，

32 位系统的内核空间占用 1G，位于最高处，剩下的 3G 是用户空间；

64 位系统的内核空间和用户空间都是 128T，分别占据整个内存空间的最高和最低处，剩下的中间部分是未定义的。

因此，结论是:

在32位操作系统上，因为进程理论上最大能申请 3 GB 大小的虚拟内存，所以直接申请 8G 内存，会申请失败。
在 64位位操作系统，因为进程理论上最大能申请 128 TB 大小的虚拟内存，即使物理内存只有 4GB，申请 8G 内存也是没问题，因为申请的内存是虚拟内存。如果这块虚拟内存被访问了，要看系统有没有 Swap 分区：
- 如果没有 Swap 分区，因为物理空间不够，进程会被操作系统杀掉，原因是 OOM（内存溢出）；
- 如果有 Swap 分区，即使物理内存只有 4GB，程序也能正常使用 8GB 的内存，进程可以正常运行；

什么是swap机制？

当系统的物理内存不够用的时候，就需要将物理内存中的一部分空间释放出来，以供当前运行的程序使用。那些被释放的空间可能来自一些很长时间没有什么操作的程序，这些被释放的空间会被临时保存到磁盘，等到那些程序要运行时，再从磁盘中恢复保存的数据到内存中。

这种将内存数据换出到磁盘，又从磁盘中恢复数据到内存的过程，就是swap机制负责的。使用 Swap 机制优点是，应用程序实际可以使用的内存空间将远远超过系统的物理内存。由于硬盘空间的价格远比内存要低，因此这种方式无疑是经济实惠的。当然，频繁地读写硬盘，会显著降低操作系统的运行速率，这也是 Swap 的弊端。

Swap换入换出的是什么类型的内存？

内核缓存的文件数据，因为都有对应的磁盘文件，所以在回收文件数据的时候，直接写回到对应的文件就可以了。但是像进程的堆、栈数据等，它们是没有实际载体，这部分内存被称为匿名页。swap换入换出的就是匿名页。

如何避免预读失效和缓存污染？

Linux操作系统的缓存

在应用程序读取文件的数据的时候，Linux 操作系统是会对读取的文件数据进行缓存的，会缓存在文件系统中的 Page Cache，Page Cache 属于内存空间里的数据，由于内存访问比磁盘访问快很多，在下一次访问相同的数据就不需要通过磁盘 I/O 了，命中缓存就直接返回数据即可。因此 Page Cache起到了加速缓存的作用。

传统的LRU算法弊端及解决方案

传统的LRU算法存在：预读失效和缓存污染的问题。

什么是预读机制？

Page Cache缓存在加载缓存页时，基于空间局部性原理，会将附近页页加载到Page Cache中，预读机制带来的好处就是减少了磁盘 I/O 次数，提高系统磁盘 I/O 吞吐量。

什么是预读失效？

如果这些被提前加载进来的页，并没有被访问，相当于这个预读工作是白做了，这个就是预读失效。对于传统的LRU算法，预读失效会导致「预读页」被加载到LRU链表前排位置，但是却没有被访问到，热点数据被驱逐。

解决方法

Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）：

active list 活跃内存页链表，这里存放的是最近被访问过（活跃）的内存页；

inactive list 不活跃内存页链表，这里存放的是很少被访问（非活跃）的内存页；

有了这两个 LRU 链表后，预读页就只需要加入到 inactive list 区域的头部，当页被真正访问的时候，才将页插入 active list 的头部。如果预读的页一直没有被访问，就会从 inactive list 移除，这样就不会影响 active list 中的热点数据。

什么是缓存污染？

当我们在批量读取数据的时候，由于数据被访问了一次，这些大量数据都会被加入到「活跃 LRU 链表」里，然后之前缓存在活跃 LRU 链表里的热点数据全部都被淘汰了，如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表就被污染了。

缓存污染的问题？

缓存污染带来的影响就是很致命的，等这些热数据又被再次访问的时候，由于缓存未命中，就会产生大量的磁盘 I/O，系统性能就会急剧下降。

解决方案

我们提高进入到活跃 LRU 链表的门槛，就能有效地保证活跃 LRU 链表里的热点数据不会被轻易替换掉。Linux 操作系统在内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 里。

进程管理

进程

我们编写的代码通过编译器会生成二进制可执行文件，当我们运行这个可执行文件后，会被装载到内存中，接着CPU会执行程序中的每一条指令，这个运行中的程序，就被称为进程。

进程的状态

当有大量处于阻塞状态的进程(进程请求某个事件且必须等待时，例如请求I/O事件)，进程会占用物理内存空间，操作系统通常会把阻塞状态的进程换出到磁盘，等需要再次运行的时候，再从硬盘换入到内存中。这就需要新的状态，来描述进程没有占用实际物理内存空间的情况，这个状态就是挂起状态。注意：导致进程挂起的原因不只因为进程所使用的内存空间不在物理内存，还包括：1. 通过sleep 让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程。 2. 用户希望挂起一个程序的执行，比如在 Linux 中用 Ctrl+Z 挂起进程。

挂起状态可以分为两种：

阻塞挂起状态：进程在外存并等待某个事件的出现；

就绪挂起状态：进程在外存，但只要进入内存，就可以立即运行。

进程的七种状态如下图所示：

进程的控制结构

在操作系统中，是用进程控制块（process control block，PCB）数据结构来描述进程的。PCB是进程存在的唯一标识。通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。

PCB包含哪些信息呢？

进程描述信息

进程标识符：标识各个进程；用户标识符：标识进程归属的用户。

进程控制和管理信息

进程的状态和优先级

资源分配清单

包括内存地址空间和虚拟地址空间信息，所打开的文件列表和I/O信息等

CPU相关信息

CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

进程的上下文切换

各个进程之间是共享 CPU 资源的，在不同的时候进程之间需要切换，让不同的进程可以在 CPU 执行，那么这个一个进程切换到另一个进程运行，称为进程的上下文切换。

CPU上下文切换？

CPU 寄存器和程序计数器 是 CPU 在运行任何任务前，所必须依赖的环境，这些环境就叫做 CPU 上下文。CPU 上下文切换就是先把前一个任务的 CPU 上下文（CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。

根据任务的不同，可以把CPU上下文切换分为：进程上下文切换、线程上下文切换、中断上下文切换。

进程是由内核管理调度的，所以进程的切换只发生在内核态。进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。 会把这些信息保存到PCB中。

进程切换的场景？

为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；

进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；

当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；

当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；

发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；

线程

线程是操作系统能独立运行的基本单位。线程是进程中的一条执行流程， 同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

线程与进程的比较

进程与线程的比较如下：

进程是资源(包括内存、打开的文件)分配的单位，线程是CPU调度的单位；
进程拥有一个完整的资源平台，线程只独享必不可少的资源，如寄存器和栈；
线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；
线程能减少并发执行的时间和空间开销；

线程比进程能减少开销，体现在?

线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；

线程的终止时间比进程快，因为线程释放的资源相比进程少很多；

同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；

由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了

线程的上下文切换

线程的上下文切换要看是否属于同一个进程：

当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据；

线程的实现

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

用户线程： 在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理；
内核线程： 在内核中实现的线程，是由内核管理的线程；
轻量级进程： 在内核中来支持用户线程；

用户线程和内核线程有:多对一、一对一、多对多的关系。

线程的用户级线程实现

用户线程的整个线程管理和调度，操作系统是不直接参与的，而是由用户级线程库函数来完成线程的管理，包括线程的创建、终止、同步和调度等。用户级线程是一种多对一的线程映射模型。

优点：

每个进程都需要有它私有的线程控制块（TCB）列表，用来跟踪记录它各个线程状态信息（PC、栈指针、寄存器），TCB 由用户级线程库函数来维护，可用于不支持线程技术的操作系统；

用户线程的切换也是由线程库函数来完成的，无需用户态与内核态的切换，所以速度特别快；

缺点：

由于操作系统不参与线程的调度，如果一个线程发起了系统调用而阻塞，那进程所包含的用户线程都不能执行了。

当一个线程开始运行后，除非它主动地交出 CPU 的使用权，否则它所在的进程当中的其他线程无法运行，因为用户态的线程没法打断当前运行中的线程，它没有这个特权，只有操作系统才有，但是用户线程不是由操作系统管理的。

由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会比较慢；

线程的内核级线程实现

内核线程是由操作系统管理的，线程对应的 TCB 自然是放在操作系统里的，这样线程的创建、终止和管理都是由操作系统负责。每个用户线程被映射或绑定到一个内核线程，是一对一的线程映射模型。

优点：

在一个进程当中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行；

CPU时间分配给线程，多线程的进程获得更多的 CPU 运行时间；

缺点：

线程的创建、终止和切换都是通过系统调用的方式来进行，因此对于系统来说，系统开销比较大；

在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息，如 PCB 和 TCB；

轻量级进程

轻量级进程（Light-weight process，LWP）是内核支持的用户线程，一个进程可有一个或多个 LWP，每个 LWP 是跟内核线程一对一映射的，也就是 LWP 都是由一个内核线程支持，而且 LWP 是由内核管理并像普通进程一样被调度。

而在LWP之上可以是用户线程，并且LWP和用户线程的对应关系可以是：一对一、多对一和多对多。

调度

选择一个进程运行这一功能是在操作系统中完成的，通常称为调度程序（scheduler）。注意：这里的进程指只有主线程的进程，所以调度主线程就等于调度了整个进程。

调度算法

单核CPU常见调度算法：

非抢占式的先来先服务(FSFS)算法 ，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。 对长作业有利，不利于短作业，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。
最短作业优先（Shortest Job First, SJF）调度算法，优先选择运行时间最短的进程来运行。对长作业不利。
高响应比优先（Highest Response Ratio Next, HRRN）调度算法，通过响应比优先级进行调度，优先级 = (等待时间+服务要求时间)/服务要求时间。由于进程要求的服务时间不可预估，所以这是理想型算法。
时间片轮转（Round Robin, RR）调度算法，每个进程被分配一个时间段，称为时间片（*Quantum*），即允许该进程在该时间段中运行。
最高优先级（Highest Priority First，HPF）调度算法：调度程序从就绪队列中选择最高优先级的进程进行运行。
多级反馈队列（Multilevel Feedback Queue）调度算法：是「时间片轮转算法」和「最高优先级算法」的综合和发展。

进程间的通信方式

每个进程的用户空间是相互独立的，但内核空间是每个进程都共享的，所以进程之间要通信必须通过内核。由于同一个进程下的线程之间都是共享进程的资源，所以线程之间更多关注的是竞争共享资源问题。

管道

Linux的|竖线就表示匿名管道，管道的传输数据是单向的，并且管道这种通信方式效率低，不适合进程间频繁的交换数据，好处就是简单，容易知道管道里的数据是否被另一个进程读取(只有被读取了，命令才会正常退出)，有名管道可以通过如下命令创建与删除：

# 创建有名管道
mkfifo pipeName
# 删除有名管道
unlink pipeName

管道的原理

匿名管道是通过系统调用int pipe(int fd[2])进行创建，返回了两个描述符，一个是管道的读取端描述符 fd[0]，另一个是管道的写入端描述符 fd[1]。注意：匿名管道是特殊的文件，只存在于内存中，不存在于文件系统中。

所谓管道，就是内核里面的一串缓存 。从管道的一段写入的数据，实际上是缓存在内核中的，另一端读取，也就是从内核中读取这段数据。另外，管道传输的数据是无格式的流且大小受限。一般可以使用fork创建子进程，创建的子进程会复制父进程的文件描述符，这样就做到了两个进程各有两个「 fd[0] 与 fd[1]」，两个进程就可以通过各自的 fd 写入和读取同一个管道文件实现跨进程通信了。不过为了避免混乱，一般父进程只保留写入的fd[1]，子进程只保留读取的fd[0]。

对于匿名管道，它的通信范围是存在父子关系的进程。因为管道没有实体，也就是没有管道文件，只能通过 fork 来复制父进程 fd 文件描述符，来达到通信的目的。

对于命名管道，它可以在不相关的进程间也能相互通信。因为命令管道，提前创建了一个类型为管道的设备文件，在进程里只要使用这个设备文件，就可以相互通信。

消息队列

消息队列可以解决管道不适合进程间频繁通信的弊端，消息队列是保存在内核中的消息链表，在发送数据时，会分成一个一个独立的数据单元，也就是消息体（数据块），消息体是用户自定义的数据类型，消息的发送方和接收方要约定好消息体的数据类型，所以每个消息体都是固定大小的存储块，不像管道是无格式的字节流数据。如果进程从消息队列中读取了消息体，内核就会把这个消息体删除。

消息队列生命周期随内核，如果没有释放消息队列或者没有关闭操作系统，消息队列会一直存在，而前面提到的匿名管道的生命周期，是随进程的创建而建立，随进程的结束而销毁。

弊端：

消息队列不适合比较大数据的传输，因为在内核中每个消息体都有一个最大长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限。

消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程。

共享内存

共享内存解决了消息队列读取和写入过程中，会发生用户态与内核态之间的消息拷贝的弊端。共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。

共享内存的弊端就是多个进程同时修改共享内存的同一块地址，会发生冲突。

信号量

共享内存会出现多进程竞争共享资源，信号量就实现了一种保护机制。

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

一个是 P 操作，这个操作会把信号量减去 1，相减后如果信号量 < 0，则表明资源已被占用，进程需阻塞等待；相减后如果信号量 >= 0，则表明还有资源可使用，进程可正常继续执行。

另一个是 V 操作，这个操作会把信号量加上 1，相加后如果信号量 <= 0，则表明当前有阻塞中的进程，于是会将该进程唤醒运行；相加后如果信号量 > 0，则表明当前没有阻塞中的进程。

P 操作是用在进入共享资源之前，V 操作是用在离开共享资源之后，这两个操作是必须成对出现的。

信号量初始化为1，表示互斥信号量，可以保证共享内存在任何时刻只有一个进程在访问，这就很好的保护了共享内存。信号量初始化为0，表示同步信号量，可以保证进程 A 应在进程 B 之前执行。

信号

上面说的进程间通信，都是常规状态下的工作模式。对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。 信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令）。

信号是进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程，一旦有信号产生，我们就有下面这几种，用户进程对信号的处理方式。

执行默认操作。Linux 对每种信号都规定了默认操作，例如，上面列表中的 SIGTERM 信号，就是终止进程的意思。

捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。

忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

Socket

要想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。 实际上，Socket 通信不仅可以跨网络与不同主机的进程间通信，还可以在同主机上进程间通信。根据创建Socket类型的不同，通信方式分为如下三种：

TCP字节流通信、UDP数据报通信、本地进程之间的通信。

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

服务端和客户端初始化 socket，得到文件描述符；

服务端调用 bind，将绑定在 IP 地址和端口;

服务端调用 listen，进行监听；

服务端调用 accept，等待客户端连接；

客户端调用 connect，向服务器端的地址和端口发起连接请求；

服务端 accept 返回用于传输的 socket 的文件描述符；

客户端调用 write 写入数据；服务端调用 read 读取数据；

客户端断开连接时，会调用 close，那么服务端 read 读取数据的时候，就会读取到了 EOF，待处理完数据后，服务端调用 close，表示连接关闭。

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

UDP 是没有连接的，所以不需要三次握手，也就不需要像 TCP 调用 listen 和 connect，但是 UDP 的交互仍然需要 IP 地址和端口号，因此也需要 bind。每次通信时，调用 sendto 和 recvfrom，都要传入目标主机的 IP 地址和端口。

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

本地字节流 socket 和本地数据报 socket 在 bind 的时候，不像 TCP 和 UDP 要绑定 IP 地址和端口，而是绑定一个本地文件，这也就是它们之间的最大区别。

多线程冲突了怎么办？

互斥与同步的概念

由于多线程执行操作共享变量的这段代码可能会导致竞争状态，因此我们将此段代码称为临界区（critical section），它是访问共享资源的代码片段，一定不能给多线程同时执行。我们希望这段代码是互斥（mutualexclusion）的，也就说保证一个线程在临界区执行时，其他线程应该被阻止进入临界区。

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

互斥与同步的实现和使用

为了实现进程/线程间正确的协作(互斥与同步)，操作系统提供了两种方式：

锁：加锁、解锁操作

信号量： P、V操作

两种方式都可以实现进程/线程之间的互斥，信号量还可以方便的实现进程/线程之间的同步。

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

锁可以分为忙等待锁和无忙等待锁：

忙等待锁，又称为自旋锁：当获取不到锁时，线程会一直占用CPU进行等待。在单处理器上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。

无等待锁，当没获取到锁的时候，就把当前线程放入到锁的等待队列，然后执行调度程序，把 CPU 让给其他线程执行。

信号量

通常信号量表示资源的数量，对应的变量是一个整型（sem）变量。另外，还有两个原子操作的系统调用函数来控制信号量的，分别是：

P 操作：将 sem 减 1，相减后，如果 sem < 0，则进程/线程进入阻塞等待，否则继续，表明 P 操作可能会阻塞；

V 操作：将 sem 加 1，相加后，如果 sem <= 0，唤醒一个等待中的进程/线程，表明 V 操作不会阻塞；

生产者消费者问题

问题描述：生产者在生成数据后，放在一个缓冲区中，消费者从缓冲区取出数据处理，任何时刻，只能有一个生产者或消费者可以访问缓冲区。

通过问题描述我们可以知道：

任何时刻只能有一个线程操作缓冲区，说明操作缓冲区是临界代码，需要互斥；

缓冲区空时，消费者必须等待生产者生成数据；缓冲区满时，生产者必须等待消费者取出数据。说明生产者和消费者需要同步。

因此我们需要三个信号量：

互斥信号量 mutex：用于互斥访问缓冲区，初始化值为 1；

资源信号量 fullBuffers：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）；

资源信号量 emptyBuffers：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n （缓冲区大小）；

经典同步问题

哲学家就餐问题

问题描述：5位哲学叫围着圆桌吃面，这个桌子只有 5 支叉子，每两个哲学家之间放一支叉子；哲学家围在一起先思考，思考中途饿了就会想进餐；哲学家只能拿到左右两边的叉子之后，才能吃面，吃完后，将叉子放回原处，继续思考。

方案一：

通过信号量的方式：

#define N 5 // 哲学家个数
semaphore fork[5]; // 信号量初始值为1，也就是叉子的个数
  
void smart_person(int i) // i为哲学家编号，0-4
{
  while(TRUE)
  {
   	think(); // 哲学家思考
    P(fork[i]); // 去拿左边叉子
    P(fork[(i+1) % N]);  // 去拿右边叉子
    eat();  // 吃饭
    V(fork[i]);  // 放下左边叉子
    V(fork[(i+1) % N]);  // 放下右边叉子
  }
}

这种解法存在一个极端的问题：假设五位哲学家同时拿起左边的叉子，桌面上就没有叉子了，这样就没有人能够拿到他们右边的叉子，也就说每一位哲学家都会在 P(fork[(i + 1) % N ]) 这条语句阻塞了，很明显这发生了死锁的现象。

方案二：

加一个互斥信号量

#define N 5 // 哲学家个数
semaphore fork[5]; // 信号量初始值为1，也就是叉子的个数
semaphore mutex: // 互斥信号量，初值为1
  
void smart_person(int i) // i为哲学家编号，0-4
{
  while(TRUE)
  {
   	think(); // 哲学家思考
    P(mutex); // 进入临界区
    P(fork[i]); // 去拿左边叉子
    P(fork[(i+1) % N]);  // 去拿右边叉子
    eat();  // 吃饭
    V(fork[i]);  // 放下左边叉子
    V(fork[(i+1) % N]);  // 放下右边叉子
    V(mutex); // 退出临界区
  }
}

该方案每次进餐只能有一位哲学家，效率太低。

解决方案：让偶数编号的哲学家「先拿左边的叉子后拿右边的叉子」，奇数编号的哲学家「先拿右边的叉子后拿左边的叉子」。 这样既不会出现死锁，也可以同时两人进餐。

#define N 5 // 哲学家个数
semaphore fork[5]; // 信号量初始值为1，也就是叉子的个数
  
void smart_person(int i) // i为哲学家编号，0-4
{
  while(TRUE)
  {
   	think(); // 哲学家思考
    
    if (i%2 == 0)
    {
      P(fork[i]); // 去拿左边叉子
    	P(fork[(i+1) % N]);  // 去拿右边叉子
    }
    else
    {
      P(fork[(i+1) % N]);  // 去拿右边叉子
      P(fork[i]); // 去拿左边叉子
    }
    
    eat();  // 吃饭
    V(fork[i]);  // 放下左边叉子
    V(fork[(i+1) % N]);  // 放下右边叉子
  }
}

读者-写者问题

问题描述：读者只会读取数据，不会修改数据，而写者即可以读也可以修改数据。「读-读」允许：同一时刻，允许多个读者同时读；「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写；「写-写」互斥：没有其他写者时，写者才能写。

方案一：

semaphore wMutex;  // 控制写操作的互斥信号量，初始值为 1
semaphore rCountMutex;  // 控制对 Rcount 的互斥修改，初始值为 1
int rCount = 0;  // 正在进行读操作的读者个数，初始化为 0

// 写者线程执行的函数
void writer(
{
  while(TRUE)
  {
    P(wMutex); // 进入临界区
    write();
    V(wMutex); // 离开临界区
  }
}
// 读者线程执行的函数
void reader()
{
  while(TRUE)
  {
  	P(rCountMutex);  // 进入临界区
    if (rCount == 0)
    {
      P(wMutex);  // 如果有写者，则阻塞写者
    }
    rCount++;  // 读者计数加1
    V(rCountMutex);  // 离开临界区
    
    read();  // 读数据
    
    P(rCountMutex);  // 进入临界区
    rCount--;  // 读完数据，准备离开
    if (rCount == 0)
    {
      V(wMutex);  // 最后一个读者离开，唤醒写者
    }
    V(rCountMutex);  // 离开临界区
  }
}

上面的这种实现，是读者优先的策略，因为只要有读者正在读的状态，后来的读者都可以直接进入，如果读者持续不断进入，则写者会处于饥饿状态。

方案二：

semaphore rCountMutex;  // 控制对 rCount 的互斥修改，初始值为 1
semaphore rMutex;  			// 控制读者进入的互斥信号量，初始值为 1

semaphore wCountMutex;  // 控制对 wCount 的互斥修改，初始值为 1
semaphore wDataMutex;  // 控制写者写操作的互斥信号量，初始值为 1

int rCount = 0;  // 正在进行读操作的读者个数，初始化为 0
int wCount = 0;  // 正在进行读操作的写者个数，初始化为 0

// 写者线程执行的函数
void writer(
{
  while(TRUE)
  {
    P(wCountMutex); // 进入临界区
    if (wCount == 0)
    {
      P(rMutex);  // 当第一个写者进入，如果有读者，则阻塞读者
    }
    wCount++;  // 写者计数加1
    V(wCountMutex);  // 离开临界区
    
    P(wDataMutex); // 写者写操作之间的互斥，进入临界区
    write();  // 写数据
    V(wDataMutex); // 离开临界区
    
    P(wCountMutex); // 进入临界区
    wCount--;  // 写完数据，准备离开
    if (wCount == 0)
    {
      V(rMutex);  // 最后一个写者离开，唤醒读者
    } 
    V(wCountMutex);  // 离开临界区
  }
}
// 读者线程执行的函数
void reader()
{
  while(TRUE)
  {
    P(rMutex);
  	P(rCountMutex);  // 进入临界区
    if (rCount == 0)
    {
      P(wDataMutex);  // 当第一个读者进入，如果有写者，则阻塞写者写操作
    }
    rCount++;  // 读者计数加1
    V(rCountMutex);  // 离开临界区
    V(rMutex);
    
    read();  // 读数据
    
    P(rCountMutex);  // 进入临界区
    rCount--;  // 读完数据，准备离开
    if (rCount == 0)
    {
      V(wDataMutex);  // 最后一个读者离开，唤醒写者写操作
    }
    V(rCountMutex);  // 离开临界区
  }
}

上述是写者优先的策略，只要有写者准备要写入，写者应尽快执行写操作，后来的读者就必须阻塞；如果有写者持续不断写入，则读者就处于饥饿；

实现公平策略的方案：方案一种读者优先策略的原因是因为，只要读者到达，就可以进入读者队列。公平的策略则是再增加一个互斥量，阻止读者的这种权限。

semaphore wDataMutex;  // 控制写者写操作的互斥信号量，初始值为 1
semaphore rCountMutex;  // 控制对 Rcount 的互斥修改，初始值为 1
semaphore flag;  // 实现公平竞争，初始值为1
int rCount = 0;  // 正在进行读操作的读者个数，初始化为 0

// 写者线程执行的函数
void writer(
{
  while(TRUE)
  {
    P(flag);
    P(wDataMutex); // 进入临界区
    write();
    V(wDataMutex); // 离开临界区
    V(flag);
  }
}
// 读者线程执行的函数
void reader()
{
  while(TRUE)
  {
    P(flag);
  	P(rCountMutex);  // 进入临界区
    if (rCount == 0)
    {
      P(wDataMutex);  // 如果有写者，则阻塞写者
    }
    rCount++;  // 读者计数加1
    V(rCountMutex);  // 离开临界区
    V(flag);
    
    read();  // 读数据
    
    P(rCountMutex);  // 进入临界区
    rCount--;  // 读完数据，准备离开
    if (rCount == 0)
    {
      V(wDataMutex);  // 最后一个读者离开，唤醒写者
    }
    V(rCountMutex);  // 离开临界区
  }
}

如何避免死锁？

死锁概念

两个线程都在等待对方释放锁，在没有外力的作用下，这些线程会一直相互等待，就没办法继续运行，这种情况就是发生了死锁。

死锁只有同时满足下面四个条件才会发生：

互斥条件：指的是多个线程不同同时使用同一资源

持有并等待条件：指的是A线程需要资源1、2，此时A线程持有了资源1，在等待资源2的同时并不会释放自己所持有的资源1。

不可剥夺条件：当线程已经持有了资源，在自己使用完之前不能被其他线程获取

环路等待条件：在死锁发生的时候，两个线程获取资源的顺序构成了环形链

避免死锁的发生

避免死锁问题就只需要破环其中一个条件就可以，最常见的并且可行的就是使用资源有序分配法，来破环环路等待条件。即线程以相同的顺序申请自己想要获取的资源。

什么是悲观锁、乐观锁？

互斥锁和自旋锁

最底层的两种锁就是互斥锁和自旋锁。这两种锁对于加锁失败后的处理方式不同：

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

自旋锁加锁失败后，线程会忙等待，直到它拿到锁；

互斥锁

互斥锁是一种独占锁，线程加锁失败后，会释放CPU给其他线程，自然线程加锁的代码就会被阻塞。该过程由操作系统内核完成，当加锁失败时，内核会将线程置为「睡眠」状态，等到锁被释放后，内核会在合适的时机唤醒线程，当这个线程成功获取到锁后，于是就可以继续执行。因此互斥锁存在一定的性能开销，会有两次线程的上下文切换成本：

当线程加锁失败时，内核会把线程的状态从「运行」状态设置为「睡眠」状态，然后把 CPU 切换给其他线程运行；

当锁被释放时，之前「睡眠」状态的线程会变为「就绪」状态，然后内核会在合适的时间，把 CPU 切换给该线程运行。

如果你能确定被锁住的代码执行时间很短，就不应该用互斥锁，而应该选用自旋锁，否则使用互斥锁。

自旋锁

自旋锁是通过 CPU 提供的 CAS 函数（Compare And Swap），在「用户态」完成加锁和解锁操作，不会主动产生线程上下文切换，所以相比互斥锁来说，会快一些，开销也小一些。CAS函数将加锁的两个步骤(查看锁是否空闲、将锁设置为当前线程持有)合并成一条硬件级指令，形成原子指令。

设锁为变量 lock，整数 0 表示锁是空闲状态，整数 pid 表示线程 ID，那么 CAS(lock, 0, pid) 就表示自旋锁的加锁操作，CAS(lock, pid, 0) 则表示解锁操作。

加锁失败的线程会忙等待，直到它拿到锁。这里的「忙等待」可以用 while 循环等待实现，不过最好是使用 CPU 提供的 PAUSE 指令来实现「忙等待」，因为可以减少循环等待时的耗电量。

注意，在单核 CPU 上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。持有锁的线程也永远无法获得CPU。自旋锁开销少，在多核系统下一般不会主动产生线程切换，适合异步、协程等在用户态切换请求的编程方式，但如果被锁住的代码执行时间过长，自旋的线程会长时间占用 CPU 资源。

读写锁

读写锁既可以选择互斥锁实现，也可以选择自旋锁来实现。由「读锁」和「写锁」两部分构成，如果只读取共享资源用「读锁」加锁，如果要修改共享资源则用「写锁」加锁。所以，读写锁适用于能明确区分读操作和写操作的场景，在读多写少的场景下能发挥出优势。

读优先锁

「读优先锁」期望的是，读锁能被更多的线程持有，以便提高读线程的并发性，它的工作方式是：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 仍然可以成功获取读锁，最后直到读线程 A 和 C 释放读锁后，写线程 B 才可以成功获取写锁。

写优先锁

「写优先锁」是优先服务写线程，其工作方式是：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 获取读锁时会失败，于是读线程 C 将被阻塞在获取读锁的操作，这样只要读线程 A 释放读锁后，写线程 B 就可以成功获取写锁。

公平读写锁

读优先锁可能会造成写线程「饿死」，而写优先锁也可能会造成读线程「饿死」。

公平读写锁比较简单的一种方式是：用队列把获取锁的线程排队，不管是写线程还是读线程都按照先进先出的原则加锁即可，这样读线程仍然可以并发，也不会出现「饥饿」的现象。

乐观锁和悲观锁

前面提到的互斥锁、自旋锁、读写锁，都是属于悲观锁。悲观锁做事比较悲观，它认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁。

乐观锁做事比较乐观，它假定冲突的概率很低，它的工作方式是：先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。乐观锁虽然去除了加锁解锁的操作，但是一旦发生冲突，重试的成本非常高，所以只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。

我们使用的Git就是采用的乐观锁思想，先让用户编辑代码，然后提交的时候，通过版本号来判断是否产生了冲突，发生了冲突的地方，需要我们自己修改后，再重新提交。

网络系统

I/O多路复用：select/poll/epoll

最基本的Socket模型

要想客户端和服务端能在网络中通信，必须使用Socket编程。创建 Socket 的时候，可以指定网络层使用的是 IPv4 还是 IPv6，传输层使用的是 TCP 还是 UDP。下面介绍基于TCP的Socket编程。

整体流程为：

服务端首先调用 socket() 函数，创建网络协议为 IPv4，以及传输协议为 TCP 的 Socket ，接着调用 bind() 函数，给这个 Socket 绑定一个 IP 地址和端口。

绑定这两个的目的是什么？

绑定端口的目的：当内核收到 TCP 报文，通过 TCP 头里面的端口号，来找到我们的应用程序，然后把数据传递给我们。

绑定 IP 地址的目的：一台机器是可以有多个网卡的，每个网卡都有对应的 IP 地址，当绑定一个网卡时，内核在收到该网卡上的包，才会发给我们；

绑定完 IP 地址和端口后，就可以调用 listen() 函数进行监听，此时对应 TCP 状态图中的 listen，如果我们要判定服务器中一个网络程序有没有启动，可以通过 netstat 命令查看对应的端口号是否有被监听。
服务端进入了监听状态后，通过调用 accept() 函数，来从内核获取客户端的连接，如果没有客户端连接，则会阻塞等待客户端连接的到来。
那客户端是怎么发起连接的呢？客户端在创建好 Socket 后，调用 connect() 函数发起连接，该函数的参数要指明服务端的 IP 地址和端口号，然后万众期待的 TCP 三次握手就开始了。

在 TCP 连接的过程中，服务器的内核实际上为每个 Socket 维护了两个队列：

一个是「还没完全建立」连接的队列，称为 TCP 半连接队列，这个队列都是没有完成三次握手的连接，此时服务端处于 syn_rcvd 的状态；

一个是「已经建立」连接的队列，称为 TCP 全连接队列，这个队列都是完成了三次握手的连接，此时服务端处于 established 状态；

当 TCP 全连接队列不为空后，服务端的 accept() 函数，就会从内核中的 TCP 全连接队列里拿出一个已经完成连接的 Socket 返回应用程序，后续数据传输都用这个 Socket。

注意，监听的 Socket 和真正用来传数据的 Socket 是两个：

一个叫作监听 Socket；

一个叫作已连接 Socket；

连接建立后，客户端和服务端就开始相互传输数据了，双方都可以通过 read() 和 write() 函数来读写数据。

基于 Linux 一切皆文件的理念，在内核中 Socket 也是以「文件」的形式存在的，也是有对应的文件描述符。

文件描述符的作用是什么？

每一个进程都有一个数据结构 task_struct，该结构体里有一个指向「文件描述符数组」的成员指针。该数组里列出这个进程打开的所有文件的文件描述符。数组的下标是文件描述符，是一个整数，而数组的内容是一个指针，指向内核中所有打开的文件的列表，也就是说内核可以通过文件描述符找到对应打开的文件。

每个文件都有一个 inode，Socket 文件的 inode 指向了内核中的 Socket 结构，在这个结构体里有两个队列，分别是发送队列和接收队列，这个两个队列里面保存的是一个个 struct sk_buff，用链表的组织形式串起来。

sk_buff 可以表示各个层的数据包，在应用层数据包叫 data，在 TCP 层我们称为 segment，在 IP 层我们叫 packet，在数据链路层称为 frame。全部数据包只用一个结构体来描述，是为了降低CPU的效率，如果每一层都定义一个数据结构，那么层之间传递数据时，就会发生拷贝。通过调整sk_buff结构体中的data指针来实现添加和去除不同层的协议首部。

如何服务更多的用户？

TCP Socket 调用流程是最简单、最基本的，它基本只能一对一通信，因为使用的是同步阻塞的方式，当服务端在还没处理完一个客户端的网络 I/O 时，或者读写操作发生阻塞时，其他客户端是无法与服务端连接的。因此我们要改进网络I/O模型，以支持更多的客户端。理论上服务器单机的最大TCP连接数量 = 客户端IP数 * 客户端端口数，但实际上会受限于以下两个方面：

文件描述符：在 Linux 下，单个进程打开的文件描述符数是有限制的，没有经过修改的值一般都是 1024

系统内存：每个 TCP 连接在内核中都有对应的数据结构，意味着每个连接都是会占用一定内存

多进程模型

服务器要支持多个客户端，其中比较传统的方式，就是使用多进程模型，也就是为每个客户端分配一个进程来处理请求。但每产生一个进程会占据一定的系统资源，并且进程的上下文切换"包袱"很大。

多线程模型

当服务器与客户端 TCP 完成连接后，通过 pthread_create() 函数创建线程，然后将「已连接 Socket」的文件描述符传递给线程函数，接着在线程里和客户端进行通信，从而达到并发处理的目的。并且可以使用线程池的方式来避免线程的频繁创建和销毁，所谓的线程池，就是提前创建若干个线程，这样当由新连接建立时，将这个已连接的 Socket 放入到一个队列里，然后线程池里的线程负责从队列中取出「已连接 Socket 」进行处理。

I/O多路复用

I/O多路复用技术，则是使用一个进程来维护多个Socket。一个进程虽然任一时刻只能处理一个请求，但是处理每个请求的事件时，耗时控制在 1 毫秒以内，这样 1 秒内就可以处理上千个请求，把时间拉长来看，多个请求复用了一个进程，这就是多路复用。

select/poll/epoll是内核提供给用户态的多路复用系统调用，进程可以通过一个系统调用函数从内核中获取多个事件。在获取事件时，先把所有连接（文件描述符）传给内核，再由内核返回产生了事件的连接，然后在用户态中再处理这些连接对应的请求即可。

select/poll

select 实现多路复用的方式是，将已连接的 Socket 都放到一个文件描述符集合，然后调用 select 函数将文件描述符集合拷贝到内核里，让内核来检查是否有网络事件产生，检查的方式很粗暴，就是通过遍历文件描述符集合的方式，当检查到有事件产生后，将此 Socket 标记为可读或可写，接着再把整个文件描述符集合拷贝回用户态里，然后用户态还需要再通过遍历的方法找到可读或可写的 Socket，然后再对其处理。

对于 select 这种方式，需要进行 2 次「遍历」文件描述符集合，而且还会发生 2 次「拷贝」文件描述符集合。

select 使用固定长度的 BitsMap(位图)，表示文件描述符集合。poll 不再用 BitsMap 来存储所关注的文件描述符，取而代之用动态数组，以链表形式来组织，突破了 select 的文件描述符个数限制，当然还会受到系统文件描述符限制。

poll 和 select 并没有太大的本质区别，都是使用「线性结构」存储进程关注的 Socket 集合，因此都需要遍历文件描述符集合来找到可读或可写的 Socket，时间复杂度为 O(n)，而且也需要在用户态与内核态之间拷贝文件描述符集合，这种方式随着并发数上来，性能的损耗会呈指数级增长。

epoll

epoll 通过两个方面，很好解决了 select/poll 的问题。

epoll 在内核里使用红黑树来跟踪进程所有待检测的文件描述字，把需要监控的 socket 通过 epoll_ctl() 函数加入内核中的红黑树里，红黑树是个高效的数据结构，增删改一般时间复杂度是 O(logn)。select/poll 每次操作时都传入整个 socket 集合给内核，而 epoll 因为在内核维护了红黑树，可以保存所有待检测的 socket ，所以只需要传入一个待检测的 socket，减少了内核和用户空间大量的数据拷贝和内存分配。

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

目录