进程管理

基础

进程

程序被编译为ELF格式存储在磁盘中，OS将它加载到内存中从第一条指令开始执行。每个运行中的程序实例被称为一个进程。

加载过程中CPU会运行别的进程，加载完毕后通过中断通知CPU。CPU允许多个进程交替执行，或者说并发执行。每个进程运行一段时间然后切换到另一个进程。

进程状态

进程的状态可以分为：运行、就绪、阻塞，以及创建和结束

当物理内存紧缺，会有部分进程的物理内存被换出到外存，这种状态被称为挂起。根据其进入挂起前的状态又可分为就绪挂起和阻塞挂起

PCB

process control block 进程控制块，标识并控制一个进程。它包含：

• 进程标识：进程ID，所属用户ID
• 进程状态：进程当前状态、进程优先级
• 资源：虚拟地址空间、打开的文件以及IO设备
• 运行上下文：寄存器值，方便恢复状态

OS通常通过链表组织相同状态的进程，例如阻塞队列、就绪队列：

进程控制

允许一个进程创建另一个进程，子进程可拷贝父进程所拥有的资源，其基本流程为：

• 创建并初始化一个空白PCB，例如填写控制信息、pid等
• 分配资源，例如内存
• 将pcb插入到就绪队列

进程有三种终止方式：正常/异常结束、kill 信号。进程终止时，父进程负责回收子进程的资源；若父进程终止子进程还在运行则子进程变为孤儿进程，被托管给1号进程回收。回收过程为：

• 寻找pcb，找到后：
  • 若处于执行状态则停止执行，让出CPU
  • 若有子进程则托管给1号进程
• 回收该进程资源，将pcb从队列中删除

进程可能需要等待事件发生，此时会阻塞自己，且只能被另一进程唤醒。阻塞的过程为：

• 找到pcb，若在运行则保存上下文，将其状态转换为阻塞状态停止运行
• 插入到阻塞队列

唤醒的过程为：找到pcb，转换状态为就绪状态，插入到就绪队列

进程切换

一个进程运行在CPU时需要自己的运行信息，即进程上下文。这包含此刻CPU中通用寄存器和PC的值、以及在内存资源等等，前者被称为CPU上下文。

每次切换进程时只需要重新加载CPU上下文即可，这被存储在pcb中。另外还需要刷新TLB，切换页表

进程调度只能发生在内核态。

线程

更小的独立运行基本单位，线程共享进程的资源。

• 这使得线程的创建&终止更快
• 同进程的线程切换无需切换页表，也更快——它们的页表一样
• 同进程的线程间通信也更快——它们的页表一样

进程和线程被 linux 统一抽象为任务，作为调度的基本单位，这意味着线程也有运行状态。

线程切换

同进程的线程切换只需要切换CPU上下文，不需要切换页表；而不同进程的线程切换还需要另外切换页表

内核线程

内核管理的线程，可被OS看到，可被调度。使用 tcb Thread Control Block 控制

优点在于一个内核线程被阻塞并不会影响其他内核线程，且相较于用户线程有更多的CPU时间

缺点在于，创建一个内核线程需要系统调用，开销较大

用户线程

非内核管理，由用户态线程库管理。OS看不到tcb，只能看到整个进程的 pcb

• 管理即创建、终止、调度、同步

多个用户线程分时共用同一个内核线程

优点在于：

• 可用于不支持线程的OS
• 切换线程快，无需转换模式

缺点在于：

• 一个线程的系统调用被阻塞，则所有用户线程都会被阻塞
• 线程不能彼此强行中止
• 时间片少，执行慢

轻量级线程 LWP

light weight process

内核支持的用户线程，一个进程可以有多个LWP。每个LWP都被一个内核线程支持，被内核像普通进程一样调度。

• CPU时间片足，syscall 不会阻塞其他线程
• 同进程LWP间切换速度相较于进程切换更快，但仍需要经过内核–切换模式！慢

调度

进程的状态变化时都会切换到调度程序，OS 通过 调度程序 scheduler 选择下一个执行的进程/线程。

一个运行中的进程可能因为：

• 使用系统调用/其他原因阻塞/退出，主动让出CPU
• 各种中断（例如CPU时间用完，被时钟中断）暂时停止运行，被迫让出CPU

切换到调度程序，更新原进程状态，选择下一个进程，切换到那个进程，继续运行

抢占式调度算法：时间片机制，时间片用完被中断切换到调度程序
非抢占式调度算法：还是会被中断，但是执行完 handler 后会返回原进程

调度原则：综合考虑CPU利用率、长任务短任务运行、等待时间、响应时间、周转时间

FCFS：先来先服务

First Come First Serve

不利于短作业的运行，等待时间长

SJF：最短作业优先

Shortest Job First

不利于长作业

HRRN：高响应比优先

Highest Response Ratio Next，等待时间相同，优先短任务；时间相同，优先等待长的；长任务等待太长了由于高响应比也有更大的出场机会

但服务时间不可预知

RR：时间片轮转

Round Robin，每个进程一个时间片，用完就换下一个，所有进程优先级相同

需要权衡时间片长短：

• 太短会产生大量上下文切换
• 太长不利于短作业

HPF：最高优先级调度算法

Highest Priority First，从就绪队列中选择优先级最高的执行。优先级可以分为：

• 静态优先级：创建进程时确定
• 动态优先级：动态变化调整优先级。例如运行时间长了则降低优先级，等待时间长了则升高优先级

根据是否抢占又可分为两种方法。

• 抢占：有更高优先级的进程出现时打断当前进程，执行优先级更高的那个进程

可能导致低优先级的进程永远不会执行

MFQ：多级反馈队列调度算法

Mutilevel Feedback Queue = 时间片 + 最高优先级

存在多个队列：

• 同优先级队列的进程FCFS
• 高优先级的队列时间片短
• 高优先级队列的进程会抢占低优先级队列的运行

短作业会被优先调度，长作业拥有更长的运行时间，兼顾二者

进程间通信

管道

单向通道，数据为连续的字节流，先入先出，一方读一方写。分为两种：

• 匿名管道：**|**，一般只有类似父子关系的进程可以通信

  

• 命名管道/FIFO：通过 mkfifo 将管道创建为文件，允许不相关的进程通信

其背后是系统调用：0读1写。一般搭配 fork 使用

写端的数据被缓存在内核中，再从读端读取。通信中一段数据需要拷贝两次，在管道满时写方进程会被阻塞在内核中，等待读方读取后，进行写入再返回继续进程运行

一般只用于读的一方会关闭fd[1]，写方会关闭fd[0]。

匿名进程被杀掉后，其中的管道数据也会消失

shell 中的 pipe

在 shell 里面执行 A | B命令的时候，A 进程和 B 进程都是 shell 创建出来的子进程，A 和 B 之间不存在父子关系，它俩的父进程都是 shell。

消息队列

• 生命周期随内核，数据保存在内核中，进程被杀掉数据依然存在，不像匿名管道
• 以消息体（即数据块）为单位传输数据，而非字节流，通信双方可预定好数据类型进行通信

它的不足在于：

• 通信数据大小有限制： 单个消息长度不能超过 MSGMNB，消息队列长度不能超过 MSGMAX
• 数据传输过程中经过了两次拷贝，且经过了两次用户态和内核态的转换。管道同理

共享内存

把一片物理内存映射到两个进程中，避免了用户态内核态的切换以及数据拷贝

一般需要锁保护

信号量

一个整型计数器，用于同步进程对共享资源的访问，保护共享数据。有两种原子操作：

• P操作：cnt–后若cnt>=0，则有资源可用，开始运行，否则阻塞
• V操作：cnt++后若cnt<=0，则有进程想要使用资源，唤醒它们；否则没有

信号量被初始化为不同值表示不同的含义：

• 1：锁/互斥信号量
• 0：同步信号量，用于多进程同步，生产/消费者模型

信号

• 可以通过信号通知进程发生了某事件，是一种异步通信机制
• 进程会打断主控制流的运行，转而去运行独立的异常控制流，也即相应的 handler。
• 进程对每个信号都有默认响应操作，也可以自定义一个 handler，进行处理或忽略
  • SIGKILL 和 SIGSTOP 无法忽略，它们用于强制中断/杀死进程

可以通过 kill -信号id pid 发送信号给进程：

• Ctrl+C 产生 SIGINT 信号，表示终止该进程；
• Ctrl+Z 产生 SIGTSTP 信号，表示停止该进程，但还未结束；

SOCKET

跨网络的进程间通信——也可以与同主机进程通信。需要通过 socket syscall：

• domain：协议族
  • AF_INET：IPV4；AF_INET6：IPV6；AF_LOCAL/AF_UNIX：本机
• type：通信特性
  • SOCK_STREAM：字节流；SOCK_DGRAM：数据报；SOCK_RAW：原始套接字
• protocal：指定通信协议，现已废除一般填0——协议已经由前面二者指定

不同的通信方式有不同的参数：

• TCP：AF_INET & SOCK_STREAM
• UDP：AF_INET & SOCK_DGRAM
• 本地进程间字节流通信：AF_LOCAL/AF_UNIX & SOCK_STREAM
• 本地进程间数据报通信：AF_LOCAL/AF_UNIX & SOCK_DGRAM

TCP 的 socket 模型

服务端：

• 初始化监听 socket，得到fd，然后把 IP和端口与fd绑定
• 调用 listen 开始监听，有请求连接的客户端时返回
• 调用 accept 建立连接，进行 TCP三次握手，成功后返回一个建立好连接的 fd
• 通过 read & write 在建立好连接的fd上通信
• 在读取到 EOF 时调用 close 断开通信

客户端：

• 创建 socket，调用 connect 请求建立连接
• 通过 read & write 通信

UDP 的 socket 模型

UDP 面向无连接，不需要三次握手，服务端不需要监听再连接

• 一般流程是双方创建好 socket 后，bind IP和端口，就开始通信了
• 通信时使用 sendto 和 recvfrom，传入目标主机的 IP和端口

本地进程通信的 socket 模型

接口与上述的字节流/数据报模型接口一致，但 bind 时需要绑定本地的一个文件

多线程冲突

防止多线程访问共享资源产生冲突，即 race condition——即便是单核也可能产生冲突，它们很可能导致结果与预期不符，且每次的结果都可能不同，难以复现，这被称为 不确定性

例如两个线程对一个变量各增加1000，每次加1；一个进程加到51时被中断，此时可能有一个值在寄存器中，然后进程2对变量进行累加，恢复到进程1时，他会把51存到变量中——这就使得进程2的工作完全作废

我们希望在操作共享资源的这段 代码临界区 中，我们对资源的操作是原子的，对其他进程的访问是互斥的

此外，进程在可能需要合作完成某件事情，为此可能需要等待，进行同步，保证一定的事件发生顺序

基本的互斥与同步策略有：锁、信号量

锁

锁的实现需要硬件提供的 test and set 原子指令，它可以原子地设置一个值并返回旧值

一般 自旋锁 的实现大概是这样：

• 另外还需要关闭中断，防止中断中的进程也试图获取锁，产生死锁

flag 表示锁是否被持有，释放锁时会把 flag 设为 0，获取锁时会设为 1。

• 自旋锁会耗费大量的CPU时间在这个循环中

睡眠锁 不需要自旋，而是在某个 channel 上睡眠，直到被唤醒

信号量

可以用于同步/互斥，取决于它们初始化的值

• 对于同步信号量，信号量常用于表示资源的数量，一般初始化为非0值
• 对于互斥信号量，信号量表示资源是否可以访问，初始化为1，表示资源空闲

其他细节。如果有三个进程共享资源，互斥信号量的值可为1、0、-1、-2

PV操作

一个进程在进入临界区前会进行P操作，并在离开临界区后进行V操作，且PV操作都是原子的

• P：Proberen（荷兰语），尝试/获取
• V：Verhogen，增加/信号

实现

具体代码实现中，信号量的结构体需要维护 信号量 & 等待队列 & 信号量的锁，锁确保访问信号量的操作是原子的

• P/wait操作：获取信号量的锁，在自己的条件变量&锁上睡眠，直到被唤醒后有资源，消耗资源，并释放锁
• V/signal操作：获取信号量的锁，资源+1，唤醒条件变量上睡眠的进程，释放锁

生产者-消费者问题

数据是资源，空位也可以是资源，再加上一把读写共享资源的锁

描述：

• 生产者生产数据后，放入缓冲区；消费者从缓冲区取出数据
• 任何时刻只能有一个线程访问缓冲区

实现时，我们需要变量：

• 缓冲区，锁/互斥信号量
• full 信号量：资源的个数，防止访问空缓冲区，资源为0时阻塞
• empty 信号量：空位个数，防止生产太快导致缓冲区溢出，空位为0时阻塞

生产者的操作为：

• 尝试获取空位资源：P(&empty)
• 获取锁进入临界区，生产数据放入缓冲区，释放锁离开临界区
• 生产数据资源：V(&full)

消费者的操作为：

• 尝试获取数据资源：P(&full)
• 获取锁进入临界区，读取缓冲区的数据，释放锁离开临界区
• 生产空位资源：V(&empty)

哲学家就餐问题

如果使用锁/互斥信号量，即每个叉子一把锁，获取叉子的锁即是用叉子。这有一种极端情形，即所有人都拿到了左边/所有人都拿到右边的叉子，试图获取另一边的叉子，但是陷入了死锁

方案1：同一时间只有一个哲学家吃饭，即吃饭前获取锁，不吃了释放锁，但这样效率会很低

方案2：避免极端情形，改变获取锁的顺序，例如奇数号哲学家先获取左边的叉子，偶数获取右边的叉子，从而避免出现上述的极端情形

方案3：确保两根叉子都可用才开始用餐

• 哲学家有三种状态：饥饿、进食、思考，每个哲学家一个互斥信号量，使用一个全局锁保护所有哲学家的状态
• 进食前哲学家先获取全局锁，查看周围两个哲学家是否在进食
  • 如果有至少一个人在进食，则进入沉睡，被唤醒后重复检查
  • 否则进入进食状态，释放全局锁
• 进食完毕后，获取全局锁，改变自身状态为思考，释放全局锁，唤醒两边的哲学家

读者写者问题

以下的锁可用互斥信号量

描述：

• 读者只会读取资源，写者可读可写
• 读读允许，读写互斥，写写互斥

方案1：读者优先，读时阻塞写

• 读者计数+计数锁+写信号量/数据锁/写锁
• 读者：
  • 获取计数锁，若未获取数据锁则获取数据锁（P），计数+1，释放计数锁
    • 读者为0时唤醒写着，所以读者为0时写者为被阻塞
  • 读取数据，获取计数锁，计数-1，若读者为0则释放数据锁（V），释放计数锁
• 写者：
  • 获取写锁（P），写数据，释放写锁（V）
• 可能饿死写者

方案2：写者优先，写时阻塞读

• 读锁+读&写计数锁+数据锁+读&写计数
  • 隔离临界区以获得更好的性能
• 写者：
  • 获取写计数锁，阻塞读者读取数据，计数+1，释放计数锁
  • 获取数据锁，写入数据，释放数据锁
  • 获取计数锁，计数–，若无写者唤醒读者，释放写锁
• 读者：
  • 获取读锁，获取读计数锁，阻塞写者写入数据，计数+1，释放读计数锁，释放读锁
  • 读取数据
  • 获取读计数锁，计数–，若无读者唤醒尝试写入数据的写者，释放读计数锁
• 读者可能饿死

方案3：公平策略

• 读计数锁+数据锁+flag锁+计数
• 写者：
  • 获取flag，获取数据锁，写入数据，释放数据锁，释放flag锁
• 读者：
  • 获取flag，获取读计数锁，阻塞写者写入，计数++，释放计数锁，释放flag
  • 读数据
  • 获取计数锁，计数–，若无读者唤醒写者写入，释放计数锁
• flag 保证了读者和写者在临界区可以相互阻塞，是一种公平的阻塞策略

死锁

两种情况：

1. 进程1持有A锁，想要获取B锁；进程2持有B锁，想要获取A锁
2. 进程持有A锁，若未关闭中断，且在中断handler中获取A锁

• 总之，都是形成环形等待链

工具：排查死锁

• pstack + gdb

两个线程同时调用了 lock，可能发生死锁。使用gdb进一步查看情况：

避免死锁

产生死锁有四大条件：

• 资源的访问是互斥的
• 线程持有锁并获取另一个锁
• 锁不可被剥夺
• 锁获取构成环形链

经典的解决方法是有序获取锁，例如在获取锁B前必然持有锁A

五种锁

获取锁都是系统调用，都需要切换到内核态

睡眠锁和自旋锁

基本上是所有锁的基础，睡眠锁获取锁失败会使进程进入睡眠，自旋锁则会不断尝试获取

• 睡眠锁会导致开启进程调度，进行上下文切换
• 自旋锁会让CPU不断进行无意义的操作，即CAS原子指令

如果临界区的代码较短，则完全可以用自旋锁；如果时间很长，则使用睡眠锁

CAS指令：比较&交换，若指定地址处的值等于预期值，则设置该地址处的值为新值，然后返回当前指定地址处的值

读写锁

读写锁基于睡眠锁和自旋锁实现，根据具体的常见选择具体的实现方式

读锁+写锁，共享锁+独占锁。适用于读多写少的场景

• 可有多个线程持有读锁
• 若写锁被持有，则读线程获取读锁的操作会被阻塞，且只有一个线程能持有写锁

根据实现，读写锁可被分为：读优先锁、写优先锁、公平锁

• 读优先锁在有读者时会阻塞写者
  • 可能会饿死写者
• 写优先锁会在有写需求时，阻塞后面的读者；有读者时会阻塞写者的数据写入操作
  • 可能饿死读者
• 公平锁不会出现饥饿的现象，他会保护临界区

乐观锁和悲观锁

前面提到的睡眠锁、自旋锁、读写锁都是悲观锁，他们假定会出现很多竞态情况，访问资源前需要上锁

乐观锁假定竞态出现的概率不高，它先修改资源，然后检查这段时间有没有冲突

• 若有冲突则放弃此次操作，否则操作完成
• 放弃后如何重试取决于业务场景，重试的成本很高，但是若概率足够低，可以接受

乐观锁是一种无锁编程，即是使用了乐观锁

• 例如在线文档的编辑，服务器要求用户提交时带上原始版本号，若和当前版本一致则接受提交，否则不接受
• 又例如 git 和 SVN

CAS与自旋锁

CAS 不是乐观锁吗，为什么基于 CAS 实现的自旋锁是悲观锁？

加了while，形成了自旋的效果

一个进程可以创建多少线程？

取决于两点：地址空间大小 & 系统参数

每次创建一个线程，内核都会为其分配一个栈空间，例如8M，可以用 ulimit -a 查看，使用 ulimit -s 调整栈空间大小

不考虑系统参数，我们可以对一个进程的线程数进行估算

• 32位系统有3G的用户虚拟空间，若一个线程栈为10M，则差不多可以创建300个线程
• 对于64位系统，这一数量可以达到一千万，理论上不会被限制，但是我们的系统可能就不支持了

系统有三个参数可能限制线程的上限：

• 系统支持的最大线程数
• 全局pid数值限制，任何大于这个值的pid都会创建失败
• 进程vma的最大数量

线程崩溃，进程也会崩溃吗？

进程崩溃的原因一般是收到了某个信号，在默认情况下 handler 都会杀死整个进程。

进程的所有线程共用一套异常处理机制，如果某个线程触发了异常，而内核发送的信号可能会导致整个进程被杀死

我们一般通过自定义信号 handler来处理每个异常，而非杀死整个进程，例如JVM的针对栈溢出和空指针异常的处理方式：