调度算法

进程调度

先来先服务

先来先服务(FCFS)算法每次运行就绪队列中最先进入的进程，直到进程退出或被阻塞，之后继续从队列中选择第一个进程接着运行

问题：
当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业

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

最短作业优先

最短作业优先(SJF)调度算法优先选择运行时间最短的进程来运行，有助于提高系统的吞吐量

问题：
对长作业不利，当就绪队列有非常多的短作业时会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行

高响应比优先

高响应比优先 (HRRN)调度算法权衡了短作业和长作业，每次进行进程调度时，先计算响应比优先级，然后把响应比优先级最高的进程投入运行
$ 优先级 = \frac{等待时间+要求服务时间}{要求服务时间} $

• 两个进程的等待时间相同时，要求的服务时间越短，优先级越高，这样短作业的进程容易被选中运行
• 两个进程要求的服务时间相同时，等待时间越长，优先级就越高，兼顾到了长作业进程，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会

问题：
实际情况下进程的要求服务时间无法确定，因此高响应比优先调度算法属于理想型算法

时间片轮转

时间片轮转(RR)调度算法是最古老、最简单、最公平且使用最广的算法
每个进程被分配一个时间段，称为时间片，允许该进程在该时间段中运行

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

问题：
时间片的长度难以确定：

• 太短会导致过多的进程上下文切换，降低 CPU 效率
• 太长可能引起对短作业进程的响应时间变长

通常时间片设为 20ms~50ms

最高优先级

最高优先级(\HPF)调度算法从就绪队列中选择最高优先级的进程进行运行

进程的优先级可以分为：

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

该算法也有两种处理优先级高的方法：

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

问题：
HPF 算法可能会导致低优先级的进程永远不会运行

多级反馈队列

多级反馈队列(Multilevel Feedback Queue)调度算法是「时间片轮转算法」和「最高优先级算法」的结合

多级 - 有多个优先级从高到低的队列，优先级越高时间片越短
反馈 - 如果有新的进程加入比当前进程优先级更高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列

1. 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度
2. 如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成
3. 如果进程在其时间片内主动释放 CPU，则优先级不变

问题

• 饥饿：如果系统有过多交互型工作，就会不断加入优先级高队列占用 CPU，导致位于优先级低队列的长工作永远无法得到 CPU
• 愚弄调度程序：用户控制进程在时间片用完之前，调用一个 I/O 操作(比如访问一个无关的文件)，从而主动释放 CPU，如此便可以始终保持在高优先级，占用更多的 CPU 时间，极端情况下(比如每运行 99%的时间片时间就主动放弃一次 CPU)可以几乎独占 CPU

解决方法：

• priority boost 机制，一段时间后将所有任务都提升到最高优先级队列，防止一直来新的任务让低优先级的长任务饿死
• 一旦工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次 CPU)，就降低其优先级，移入低一级队列

内存页面置换

最佳页面置换算法

最佳页面置换算法(OPT)选择在「未来」最长时间不访问的页面进行置换

该算法计算内存中每个逻辑页面的下一次访问时间，然后比较，选择未来最长时间不访问的页面进行置换

属于理想算法，现实无法实现

先进先出置换算法

先进先出置换算法(FIFO)选择在内存驻留时间最长的页面进行置换

问题：

• 经常访问或者需要长期存在的页面会被频繁调入调出 - 较早调入的页往往是经常被访问或者需要长期存在的页，这些页会被反复调入和调出
• 存在 Belady 现象 - 被置换的页面并不是进程不会访问的，有时就会出现分配的页面数增多但缺页率反而提高的异常现象，出现该异常的原因是因为 FIFO 算法只考虑了页面进入内存的顺序，而没有考虑页面访问的频率和紧迫性

最近最久未使用置换算法

最近最久未使用置换算法(LRU)选择最长时间没有被访问的页面进行置换

问题：
开销大，需要在内存中维护一个所有页面的链表，且每次访问内存时必须更新整个链表

时钟页面置换算法

时钟页面置换算法(Lock)把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面

当发生缺页中断时检查表针指向的页面：

• 如果访问位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置
• 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止

最不常用置换算法

最不常用置换算法(LFU)选择访问次数最少的页面进行置换

实现方式：
对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器累加 1，发生缺页中断时淘汰计数器值最小的那个页面

问题：

• 计数器硬件成本较高
• 对计数器进行查找耗时
• LFU 算法只考虑频率问题而忽略时间问题，过去时间里高访问频率的停用页面置换优先可能低于当前频繁访问的页面
  • 可以定期减少访问的次数，加大旧页面被置换的概率

磁盘调度

磁盘调度算法通过优化磁盘的访问请求顺序提高磁盘的访问性能

寻道的时间是磁盘访问最耗时的部分

先来先服务算法

先来先服务算法按请求顺序访问磁道

最短寻道时间优先算法

最短寻道时间优先(SSF)算法优先选择从当前磁头位置所需寻道时间最短的请求

问题：
可能出现饥饿问题，对于动态请求磁头始终在一小块区域来回移动，远处请求始终未响应

扫描算法

扫描算法(Scan)下磁头在一个方向上移动并访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，调换方向访问之前的请求

问题：
中间部分的磁道相比其他部分响应频率更高

循环扫描算法

循环扫描算法(CSCAN)在扫描算法基础上规定磁道只响应一个方向上的请求
只有磁头朝特定方向移动时才处理磁道访问请求，返回时直接快速移动至最靠边缘的磁道(复位磁头)，该过程速度快

LOOK 与 C-LOOK 算法

扫描算法需要移动到磁盘的最始端或最末端
LOOK 算法下磁头在移动到「最远的请求」位置，然后立即反向移动
C-LOOK 算法下磁头在反向移动的情况下不响应请求

悲观锁&乐观锁

悲观锁认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁
乐观锁假定冲突的概率很低，先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作

乐观锁也叫无锁编程，全程不加锁

锁

锁类型

悲观锁&乐观锁

悲观锁认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁
乐观锁假定冲突的概率很低，先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作

乐观锁也叫无锁编程，全程不加锁

互斥锁&自旋锁

当已经有一个线程加锁后，其他线程加锁则就会失败

互斥锁加锁失败后，线程会释放 CPU 给其他线程
自旋锁加锁失败后，线程会占据 CPU 忙等待直到拿到锁

互斥锁是一种独占锁，加锁失败时由操作系统内核实现阻塞

互斥锁存在两次线程上下文切换，因此当加锁执行的代码执行时间较短时，应选用自旋锁减小开销

自旋锁通过 CPU 提供的 CAS 函数完成加锁

1. 查看锁的状态
2. 如果锁处于空闲状态，将锁设置为当前线程持有

CAS 函数将两个步骤合并成一条硬件级指令，形成原子指令，这样就保证了这两个步骤是不可分割的，要么一次性执行完两个步骤，要么两个步骤都不执行
CAS 本身为乐观锁，但自旋锁为借助 CAS 实现的悲观锁

在单核 CPU 上使用自旋锁需要抢占式的调度器(即不断通过时钟中断一个线程，运行其他线程)，因为一个自旋的线程永远不会放弃 CPU

读写锁

当写锁没有被线程持有时，多个线程能够并发地持有读锁
一旦写锁被线程持有后，其他线程对于读锁和写锁的获取都会阻塞

读写锁适用于读多写少的场景

读写锁又可分为读优先锁和写优先锁

• 读优先锁在读锁被持有时阻塞写锁，同时允许新读锁的获取
• 写优先锁在存在被阻塞的写锁时，不允许其他线程获取新读锁

读优先锁和写优先锁都可能会产生饥饿问题，因此需要公平读写锁
公平读写锁比较简单的一种方式是：用队列把获取锁的线程排队，不管是写线程还是读线程都按照先进先出的原则加锁

死锁

计算机操作系统 - 死锁 | CS-Notes 面试笔记 (cyc2018.xyz)

死锁条件

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

• 互斥 - 多个线程不能同时使用同一个资源
• 占有并等待 - 线程在等待时不释放自己已持有的资源
• 不可抢占 - 当资源已被线程持有时，在该线程使用完之前不能被其他线程获取
• 循环等待 - 两个线程获取资源的顺序构成了环形链

死锁检测

每种类型一个资源的死锁检测

绘制资源分配图，方框表示资源，圆圈表示进程
资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源
图 a 可以抽取出环如图 b，满足了环路等待条件，因此会发生死锁

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生

每种类型多个资源的死锁检测

上图中，有三个进程四个资源，每个数据代表的含义如下：

E 向量：资源总量
A 向量：资源剩余量
C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
R 矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

1. 每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程
2. 寻找一个没有标记的进程 Pi，它所请求的资源与其拥有资源之和小于等于 A
3. 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1
4. 如果没有这样一个进程，算法终止

死锁解决

解决死锁问题只需要破坏其中一个条件

1. 破坏互斥条件
   • 使资源可以同时访问，例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程
2. 破坏占有和等待条件
   • 静态分配策略，规定所有进程在开始执行前需申请到所需要的全部资源
3. 破坏不可抢占条件
4. 破坏环路等待
   • 资源有序分配，给资源统一编号，进程只能按编号顺序来请求资源

避免死锁还可将系统的状态分为 安全状态 和 不安全状态 ，每当在未申请者分配资源前先测试系统状态，若把系统资源分配给申请者会产生死锁，则拒绝分配，否则接受申请，并为它分配资源

解决死锁问题的另一条途径是死锁检测和解除，对资源的分配不加以任何限制，也不采取死锁避免措施，但系统定时运行死锁检测程序，判断系统内是否出现死锁，如果检测到系统发生了死锁，再采取措施去解除它
常用的解除死锁的方法有以下四种：

• 立即结束所有进程的执行，重新启动操作系统 - 简单，但以前所在的工作全部作废，损失很大
• 撤销涉及死锁的所有进程，解除死锁后继续运行 - 彻底打破死锁的循环等待条件，但将损失进程的前期工作
• 逐个撤销涉及死锁的进程，回收其资源直至死锁解除
• 抢占资源 - 从涉及死锁的一个或几个进程中抢占资源，把夺得的资源再分配给涉及死锁的进程直至死锁解除

银行家算法

当一个进程申请使用资源的时候，银行家算法通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待

安全性算法
假设资源 P1 申请资源，若申请的资源数量小于等于空闲资源数量，银行家算法先试探的分配给它，然后接着判断分配给 P1 后剩余的资源，能不能使进程队列的某个进程执行完毕

• 若没有进程可执行完毕，则系统处于不安全状态
• 若有进程可执行完毕，则假设回收已分配给它的资源(空闲资源数量增加)，把这个进程标记为可完成，并继续判断队列中的其它进程
  • 若所有进程都可执行完毕，则系统处于安全状态，并根据可完成进程的分配顺序生成安全序列

银行家算法改善了 资源使用率低的问题 ，但是它要不断地检测每个进程对各类资源的占用和申请情况，以及做 安全性检查 ，时间开销较大

进程管理

5.1 进程、线程基础知识 | 小林coding (xiaolincoding.com)

进程

进程是 CPU 中运行的一个程序

运行状态

在一个进程的活动期间至少具备三种基本状态

• 运行状态：该时刻进程占用 CPU 运行
• 就绪状态：进程可运行，但由于其他进程处于运行状态而暂时停止运行
• 阻塞状态：进程正在等待某一事件发生(如等待 I/O 操作的完成)而暂时停止运行，这时即使得到 CPU 控制权该进程也无法运行

进程还有另外两个基本状态：

• 创建状态：进程正在被创建时的状态
• 结束状态：进程正在从系统中消失时的状态

在操作系统的虚拟内存管理中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存
挂起状态用于描述进程没有占用实际的物理内存空间的情况，同时又分为两种：

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

僵尸进程 & 孤儿进程

通常子进程由父进程创建，但二者的结束顺序不一定

• 如果父进程先退出， ⽗进程没有调⽤ wait() 或者 waitpid() 函数等待⼦进程完成再退出，则剩下的⼦进程会被 init(pid=1)进程接收，成为孤⼉进程
• 如果⼦进程先退出了，⽗进程还未结束并且没有调⽤ wait() 或者 waitpid() 函数获取⼦进程的状态信息，则⼦进程残留的状态信息(task_struct 结构和少量资源信息)会变成僵⼫进程

查看方式
Linux 下可使用 top 命令查看，zombie 值代表僵尸进程的数量

危害

• 僵尸进程占据 PID，如果大量的产生僵尸进程，将因为没有可用的进程号而导致系统不能产生新的进程
• 僵尸进程的内核栈无法释放

解决方案
在 Linux 系统中，避免僵尸进程的方法包括：

• 直接调用 wait 或 waitpid 函数：在父进程中调用 wait 或 waitpid 函数，等待子进程结束并返回状态码，这样可以确保子进程退出后，其资源能够被正常回收，避免产生僵尸进程
• 使用信号处理程序：在父进程中注册 SIGCHLD 信号处理程序，当子进程结束时会向父进程发送该信号，父进程可以在信号处理程序中调用 wait 或 waitpid 函数回收子进程资源
• fork 两次：第一次 fork 的子进程在第二次 fork 完成后直接退出，这样第二次 fork 得到的子进程没有父进程而自动被 init 进程收养，init 会负责释放它的资源

在进程退出的时候，内核释放该进程所有的资源，包括打开的文件，占用的内存等，但是仍然为其保留一定的信息(包括进程号，退出状态，运行时间等)，直到父进程通过 wait/waitpid 来取时才释放
如果进程不调用 wait/waitpid 的话，那么保留的那段信息就不会释放，其进程号就会一直被占用，但是系统所能使用的进程号有限

控制结构

操作系统中用进程控制块(PCB)数据结构来描述进程

PCB 是进程存在的唯一标识，包含以下信息

• 进程描述信息
  • 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符
  • 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务
• 进程控制和管理信息
  • 进程当前状态，如 new、ready、running、waiting 或 blocked 等
  • 进程优先级：进程抢占 CPU 时的优先级
• 资源分配清单
  • 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息
• CPU 相关信息：
  • CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行

操作系统以链表的形式连接 PCB，对状态相同的进程进行管理

控制过程

创建进程

操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程所拥有的资源
创建进程的过程如下：

1. 分配一个唯一的进程 ID
2. 为该进程创建一个空白的 PCB，并填充 PCB 内相关进程信息
3. 为该进程分配运行时所必需的资源，比如内存资源
4. 将 PCB 插入到就绪队列，等待被调度运行

终止进程

进程可以有 3 种终止方式：正常结束、异常结束以及外界干预(信号 kill 掉)

当子进程被终止时，其在父进程处继承的资源应当还给父进程
而当父进程被终止时，该父进程的子进程就变为孤儿进程，会被 1 号进程收养，并由 1 号进程对它们完成状态收集工作

终止进程的过程如下：

1. 查找需要终止的进程的 PCB
2. 如果处于执行状态，则立即终止该进程的执行，然后将 CPU 资源分配给其他进程
3. 如果其还有子进程，则应将该进程的子进程交给 1 号进程接管
4. 将该进程所拥有的全部资源都归还给操作系统
5. 将其从 PCB 所在队列中删除

阻塞进程

当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待，它只能由另一个进程唤醒。

阻塞进程的过程如下：

1. 找到将要被阻塞进程标识号对应的 PCB
2. 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行
3. 将该 PCB 插入到阻塞队列中去

唤醒进程

进程由运行转变为阻塞状态是由于进程必须等待某一事件的完成，所以处于阻塞状态的进程是绝对不可能叫醒自己的

如果某进程正在等待 I/O 事件，需由别的进程发消息给它，则只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它

唤醒进程的过程如下：

1. 在该事件的阻塞队列中找到相应进程的 PCB
2. 将其从阻塞队列中移出，并置其状态为就绪状态
3. 把该 PCB 插入到就绪队列中，等待调度程序调度

进程的阻塞和唤醒是一对功能相反的语句，如果某个进程调用了阻塞语句，则必有一个与之对应的唤醒语句

Linux 进程通信

每个进程的用户地址空间相互独立的，通常不能互相访问，所有进程共享内核空间，因此进程之间必须通过内核进行通信

管道

管道实际为内核中的一段缓存，传输的数据是无格式的流，且大小受限
当向管道中写入数据时进程阻塞，直到另一进程从管道中读取数据

linux 可直接使用 | 作为匿名管道进行 "单向" 传输数据
匿名管道是特殊文件，只存在于内存而不存在于文件系统中
匿名管道只能用于存在父子关系的进程或兄弟进程间通信，生命周期随着进程创建而建立，随着进程终止而消失

ps auxf | grep mysql

采用 mkfifo 可创建 "数据先进先出" 的命名管道
命名管道以磁盘文件形式存在，其在文件系统创建一个设备文件，任意两个进程可以通过这个设备文件进行通信

消息队列

消息队列是保存在内核中的消息链表，传输的数据为用户自定义的数据类型消息体

进程异步写入消息队列后正常返回，另一进程需要时从消息队列中读取数据

缺点：

• 消息体大小受限，消息队列最大长度受限
• 通信过程中发生用户态和内核态之间的数据拷贝开销

共享内存

共享内存在物理内存中分配一个共享空间，不同进程使用一块虚拟地址空间映射至该相同的共享空间，每个进程可以直接访问，速度快，无拷贝开销，但需考虑多进程竞争带来的数据错乱

信号量

信号量是一个整型的计数器，主要用于实现进程间的互斥与同步以保护共享资源，而不是用于缓存进程间通信的数据

信号量表示资源的数量，控制信号量的方式有两种原子操作：

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

为什么需要信号量？

1. 信号量不一定是锁定某一个资源，而是流程上的概念，比如：有 A,B 两个线程，B 线程要等 A 线程完成某一任务以后再进行自己下面的步骤，这个任务并不一定是锁定某一资源，还可以是进行一些计算或者数据处理之类。而线程互斥量则是“锁住某一资源”的概念，在锁定期间内，其他线程无法对被保护的数据进行操作
2. 信号量可以设置大于 1 的值，用于控制可以同时并发访问的线程数，比如可以控制同时有 5 个爬虫线程

信号

对于异常情况下的工作模式，用信号的方式来通知进程
信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件
Linux 操作系统中为了响应各种各样的事件，提供了多种信号

$ kill -l
HUP INT QUIT ILL TRAP IOT BUS FPE KILL USR1 SEGV USR2 PIPE ALRM TERM STKFLT CHLD CONT STOP TSTP TTIN TTOU URG XCPU XFSZ VTALRM PROF WINCH POLL PWR SYS

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

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

Socket 套接字

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 参数原本是用来指定通信协议的，但现在基本废弃，因为协议已经通过前面两个参数指定完成，protocol 目前一般写成 0 即可

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

1. 服务端和客户端初始化用于监听的 socket，得到文件描述符
2. 服务端调用 bind，将用于监听的 socket 绑定在 IP 地址和端口
3. 服务端调用 listen 进行监听
4. 服务端调用 accept 等待客户端连接
5. 客户端调用 connect 向服务器端的地址和端口发起连接请求
6. 服务端 accept 返回用于传输的 socket 的文件描述符
7. 客户端调用 write 写入数据；服务端调用 read 读取数据
8. 客户端断开连接时调用 close
9. 服务端 read 读取数据时读取到 EOF，待处理完数据后，服务端调用 close，表示连接关闭

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

对于 UDP 来说，不需要要维护连接，那么也就没有所谓的发送方和接收方，甚至都不存在客户端和服务端的概念，只要有一个 socket 多台机器就可以任意通信，因此每一个 UDP 的 socket 都需要 bind

另外，每次通信调用 sendto 和 recvfrom 时都要传入目标主机的 IP 地址和端口。

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

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

调度

操作系统通过调度程序(scheduler) 选择运行的程序

调度时机

在进程的生命周期中，当进程状态变化时会触发一次调度

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

• 非抢占式调度算法挑选一个进程运行，直到该进程被阻塞或者进程退出才会调用另外一个进程，忽视时钟中断事件
• 抢占式调度算法挑选一个进程运行，在时间间隔的末端发生时钟中断，把 CPU 控制返回给调度程序进行调度，如果此时该进程仍在运行，调度程序将该进程挂起并从就绪队列中挑选另外一个进程运行，也就是常说的时间片机制

调度原则

原则一：如果运行的程序，发生了 I/O 事件请求，进程阻塞等待硬盘的数据返回，会造成 CPU 突然的空闲
所以，为了提高 CPU 利用率，在 I/O 事件请求致使 CPU 空闲的情况下，调度程序需要从就绪队列中选择一个进程来运行

原则二：有的程序执行某个任务花费的时间会比较长，如果这个程序一直占用着 CPU，会造成系统吞吐量(CPU 在单位时间内完成的进程数量)的降低
所以，要提高系统的吞吐率，调度程序要权衡长任务和短任务进程的运行完成数量

原则三：从进程开始到结束的过程中，实际上是包含两个时间，分别是进程运行时间和进程等待时间，这两个时间总和就称为周转时间，进程的周转时间越小越好
所以，如果进程的等待时间很长而运行时间很短，那周转时间就很长，这不是我们所期望的，调度程序应该避免这种情况发生

原则四：处于就绪队列的进程不能等太久，等待的时间越短越好，这样可以使得进程更快的在 CPU 中执行
所以，就绪队列中进程的等待时间也是调度程序所需要考虑的原则

原则五：对于鼠标、键盘这种交互式比较强的应用，我们当然希望它的响应时间越快越好，否则就会影响用户体验了
所以，对于交互式比较强的应用，响应时间也是调度程序需要考虑的原则

针对上面的五种调度原则，总结如下：

• CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，提高 CPU 的利用率
• 系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量
• 周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好
• 等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意
• 响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准

调度算法

!1e-调度算法#进程调度

线程

线程是进程当中的一条执行流程

同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的

实现

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

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

用户线程

用户线程基于用户态的线程管理库实现，线程控制块(TCB)也在库里实现，对于操作系统不可见，操作系统只能看到整个进程的 PCB

用户级线程的模型下多个用户线程对应同一个内核线程

优点

• 管理开销小 - 创建、销毁不需要系统调用
• 切换成本低 - 用户线程的切换也是由线程库函数来完成的，无需用户态与内核态的切换，所以速度特别快
• 应用范围广 - 每个进程都需要有私有的线程控制块(TCB)列表，用来跟踪记录该进程中各个线程的状态信息(PC、栈指针、寄存器)，TCB 由用户级线程库函数维护，可用于不支持线程技术的操作系统

缺点

• 资源浪费 - 由于操作系统不参与线程的调度，如果一个线程发起了系统调用而阻塞，那进程所包含的用户线程都不能执行
• 当一个线程开始运行后，除非它主动地交出 CPU 的使用权，否则它所在的进程当中的其他线程无法运行，因为用户态的线程没法打断当前运行中的线程，它没有这个特权，只有操作系统才有，但是用户线程不是由操作系统管理的
• 执行时间短 - 由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会比较慢
• 线程间协作成本高：两个线程通信需要 I/O，I/O 需要系统调用，因此用户态线程需要支付额外的系统调用成本

内核线程

内核线程由操作系统管理，线程对应的 TCB 位于操作系统中，线程的创建、终止和管理都由操作系统负责

内核线程的模型下一个用户线程对应一个内核线程

优点

• 在一个进程当中，如果某个内核线程发起系统调用而被阻塞，不会影响其他内核线程的运行
• CPU 时间片分配给线程，多线程的进程获得更多的 CPU 运行时间

缺点

• 切换开销大 - 在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息，如 PCB 和 TCB，由于内核线程运行在内核态，每次在内核态与用户态切换时，需要进行上下文切换。这种切换开销比较大，会降低内核线程的性能
• 创建成本高 - 线程的创建、终止和切换都是通过系统调用的方式来进行，系统需要维护一张内核线程表，实时维护每个线程的状态。每次调度线程时，需要进行复杂的处理和判断，开销比较大

轻量级进程

轻量级进程(LWP)是是一种由内核支持的用户线程，是基于内核线程的高级抽象，只有先支持内核线程，才能有 LWP，一个进程可有一个或多个 LWP，每个 LWP 都由一个内核线程支持，跟内核线程一对一映射，且 LWP 由内核管理，并像普通进程一样被调度

在大多数系统中，LWP 与普通进程的区别在于它只有一个最小的执行上下文和调度程序所需的统计信息
一般来说，一个进程代表程序的一个实例，而 LWP 代表程序的执行线程，因为一个执行线程不像进程那样需要那么多状态信息，所以 LWP 也不带有这些信息

缺点

• 大多数 LWP 的操作，如建立、析构以及同步，都需要进行系统调用。系统调用的代价相对较高：需要在用户态和内核态中切换
• 每个 LWP 都需要有一个内核线程支持，因此 LWP 要消耗内核资源(内核线程的栈空间)。因此一个系统不能支持大量的 LWP

在 LWP 之上也是可以使用用户线程的，那么 LWP 与用户线程的对应关系就有三种：

• 1 : 1，即一个 LWP 对应一个用户线程
  • 优点：实现并行，当一个 LWP 阻塞，不会影响其他 LWP
  • 缺点：每一个用户线程，就产生一个内核线程，创建线程的开销较大
• N : 1，即一个 LWP 对应多个用户线程
  • 优点：用户线程要开几个都没问题，且上下文切换发生用户空间，切换的效率较高
  • 缺点：一个用户线程如果阻塞了，则整个进程都将会阻塞，另外在多核 CPU 中，是没办法充分利用 CPU 的
• M : N，即多个 LWP 对应多个用户线程
  • 优点：综合了前两种优点，大部分的线程上下文发生在用户空间，且多个线程又可以充分利用多核 CPU 的资源组合，结合 1:1 模型和 M:N 模型，开发人员可以针对不同的应用特点调节内核线程的数目来达到物理并行性和逻辑并行性的最佳方案

多线程

同一进程下的多线程之间可以共享进程的资源，比如代码段、堆空间、数据段、打开的文件等，但每个线程都有自己独立的栈空间

最大数量

• 32 位系统，用户态的虚拟空间只有 3G，如果创建线程时分配的栈空间是 10M，那么一个进程最多只能创建 300 个左右的线程
• 64 位系统，用户态的虚拟空间大到有 128T，理论上不会受虚拟内存大小的限制，而会受系统的参数或性能限制

线程同步

锁

!1c1-锁#互斥锁&自旋锁

!1c1-锁#读写锁

条件变量

条件变量为什么要和互斥锁一起使用_条件变量为什么要和锁一起用_一只牛_007的博客-CSDN博客

条件变量是利用线程间共享的全局变量进行同步的一种机制，用于自动阻塞一个线程，直到某特殊情况发生为止

一个条件变量可以完成以下两项操作：

• 阻塞多个线程，直至接收到“条件成立”的信号，这些线程会组成一个等待队列
• 当条件成立时，向等待队列中的一个或所有线程发送信号，解除它们的“被阻塞”状态

为了避免解除阻塞后的多线程之间发生“抢夺资源”的问题，条件变量在使用过程中必须和一个互斥锁搭配使用
当条件不满足时，线程往往解开相应的互斥锁并等待条件发生变化，一旦其他的某个线程改变了条件变量，将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程，这些线程将重新锁定互斥锁并重新测试条件是否满足，如果满足则解除阻塞，不满足则继续阻塞等待唤醒

条件变量 VS 互斥锁
互斥锁要求未获取到锁的线程不断主动尝试获取锁，比较消耗系统资源
条件变量会在发生改变时通知唤醒阻塞线程，线程被唤醒后，它将重新检查判断条件是否满足，如果还不满足，该线程就休眠了，应该仍阻塞在这里，等待条件满足后被唤醒，节省了线程不断运行浪费的资源

信号量

!#信号量

信号量和条件变量有何不同?

1. 信号量自身 wait 和 signal 的原子操作保证了 value 的同步，条件变量只能多添加一个互斥量来实现 value 的同步
2. 信号量只能一次唤醒一个特定的进程，条件变量可以广播，广播的存在使得信号量内部使用 if 判断，条件变量使用 while 判断
3. 信号量内部定义 value 具有局限性，即只能对 int 类型资源的变化进行同步，条件变量可使用多种类型 value
4. 如果用信号量，当 wait(s)的时候，默认了“我使用 s，并且根据情况判断是否等待 s”，但如果用条件变量，就只有一个语义，就是“我等待 s”，而并不必须使用 s

屏障

屏障是一种同步原语，允许每个线程等待，直到所有的合作线程都达到某一点，然后从该点继续执行

事件

Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作

进程 VS 线程 (VS 协程)

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

线程开销比进程小

• 线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们
• 线程的终止时间比进程快，因为线程释放的资源相比进程少很多
• 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间(虚拟内存共享)，也即同一个进程下的线程都具有同一个页表，在切换的时候不需要切换页表，对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的
• 同一个进程内的线程间数据交互效率比进程高，因为同一个进程内的线程共享内存和文件资源，在线程之间传递数据时不需要经过内核

上下文切换

进程是由内核管理和调度的，所以进程的切换只能发生在内核态
进程切换分两步：

1. 切换「页表」以使用新的地址空间
2. 切换内核栈和 CPU 上下文

进程切换场景：

• 当某个进程的 CPU 时间片耗尽时，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行
• 进程在系统资源不足(比如内存不足)时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行
• 当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，也会重新调度
• 当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行
• 发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序

线程切换时，因为虚拟内存是共享的，所以只需要切换线程的私有数据、寄存器等不共享的数据

差异原因：
每个进程都有自己的虚拟地址空间，因此每个进程都有自己的页表，当进程切换后页表也要进行切换，页表切换后 TLB 缓存失效导致命中率降低，虚拟地址转换为物理地址变慢，表现出来的就是程序运行会变慢
而线程切换则不会导致 TLB 失效，因为线程无需切换地址空间，因此通常说线程切换要比较进程切换快