dsfds' blog

学海无涯，回头是岸

0%

『OS』进程管理

发表于 更新于 Valine：

状态之间的转移：

进程五种状态的变迁

如果有大量处于阻塞状态的进程，进程可能会占用着物理内存空间，显然不是我们所希望的，毕竟物理内存空间是有限的，被阻塞状态的进程占用着物理内存就一种浪费物理内存的行为。

所以，在虚拟内存管理的操作系统中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存。

那么，就需要一个新的状态，来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态。这跟阻塞状态是不一样，阻塞状态是等待某个事件的返回。

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

七态模型：

七种状态变迁

进程的控制结构

PCB，数据结构来描述进程。

PCB 是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。

PCB中有哪些信息呢？

进程描述信息：

  • 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
  • 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；

进程控制和管理信息：

  • 进程当前状态，如 new、ready、running、waiting 或 blocked 等；
  • 进程优先级：进程抢占 CPU 时的优先级；

资源分配清单：

  • 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。

CPU 相关信息：

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

通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。

  • 将所有处于就绪状态的进程链在一起，称为就绪队列；
  • 把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；
  • 另外，对于运行队列在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。

进程控制

创建：

  • 申请一个空白的 PCB，并向 PCB 中填写一些控制和管理进程的信息，比如进程的唯一标识等；
  • 为该进程分配运行时所必需的资源，比如内存资源；
  • 将 PCB 插入到就绪队列，等待被调度运行；

终止：

3 种终止方式：正常结束、异常结束以及外界干预（信号 kill 掉）。

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

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

阻塞：

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

唤醒：

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

上下文切换

CPU 寄存器和程序计数是 CPU 在运行任何任务前，所必须依赖的环境，这些环境就叫做 CPU 上下文。

上面说到所谓的「任务」，主要包含进程、线程和中断。所以，可以根据任务的不同，把 CPU 上下文切换分成：进程上下文切换、线程上下文切换和中断上下文切换。

就是切换寄存器状态🐕。

所以，进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。

何时发生切换：

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

总结：时间片用完；系统资源不足；sleep主动切换；高优先级进程中断；硬件中断。

线程

那到底如何解决呢？需要有一种新的实体，满足以下特性：

  • 实体之间可以并发运行；
  • 实体之间共享相同的地址空间；

这个新的实体，就是线程( *Thread* )，线程之间可以并发运行且共享相同的地址空间。

其实是有场景的，需要共享许多资源的并发任务放在进程中不同线程是比较好的。

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

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

线程的优点：

  • 一个进程中可以同时存在多个线程；
  • 各个线程之间可以并发执行；
  • 各个线程之间可以共享地址空间和文件等资源；

线程的缺点：

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

比较进程与线程

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

开销的减少，体现在：

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

线程的上下文切换？

线程实现

  • 用户线程（*User Thread*）：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理；
  • 内核线程（*Kernel Thread*）：在内核中实现的线程，是由内核管理的线程；
  • 轻量级进程（*LightWeight Process*）：在内核中来支持用户线程；

关于用户线程：

用户线程是基于用户态的线程管理库来实现的，那么线程控制块（*Thread Control Block, TCB*） 也是在库里面来实现的，对于操作系统而言是看不到这个 TCB 的，它只能看到整个进程的 PCB。

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

用户可以自己管理线程。

用户线程的优点：

  • 每个进程都需要有它私有的线程控制块（TCB）列表，用来跟踪记录它各个线程状态信息（PC、栈指针、寄存器），TCB 由用户级线程库函数来维护，可用于不支持线程技术的操作系统；
  • 用户线程的切换也是由线程库函数来完成的，无需用户态与内核态的切换，所以速度特别快；

用户线程的缺点：

  • 由于操作系统不参与线程的调度，如果一个线程发起了系统调用而阻塞，那进程所包含的用户线程都不能执行了。
  • 当一个线程开始运行后，除非它主动地交出 CPU 的使用权，否则它所在的进程当中的其他线程无法运行，因为用户态的线程没法打断当前运行中的线程，它没有这个特权，只有操作系统才有，但是用户线程不是由操作系统管理的。
  • 由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会比较慢；

关于内核线程

内核线程是由操作系统管理的，线程对应的 TCB 自然是放在操作系统里的，这样线程的创建、终止和管理都是由操作系统负责。

内核线程的优点：

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

内核线程的缺点：

  • 在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息，如 PCB 和 TCB；
  • 线程的创建、终止和切换都是通过系统调用的方式来进行，因此对于系统来说，系统开销比较大；

关于轻量级进程（LWP）

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

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

LWP 模型

调度

在进程的生命周期中，当进程从一个运行状态到另外一状态变化的时候，其实会触发一次调度。

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

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

  • 非抢占式调度算法挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另外一个进程，也就是说不会理时钟中断这个事情。
  • 抢占式调度算法挑选一个进程，然后让该进程只运行某段时间，如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列挑选另外一个进程。这种抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把 CPU 控制返回给调度程序进行调度，也就是常说的时间片机制。

调度原则：

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

调度算法：

FCFS

SJF

HRRN

RR

HPF

多级反馈：综合了时间片轮转（RR）和最高优先级（HPF）的方法。

银行家算法。

进程间的通信

管道

消息队列

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

消息队列的读取和写入的过程，都会有发生用户态与内核态之间的消息拷贝过程。

共享内存

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。

信号量

信号量其实是一个整型的计数器，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。

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

可以发现，信号初始化为 1，就代表着是互斥信号量，它可以保证共享内存在任何时刻只有一个进程在访问，这就很好的保护了共享内存。

可以发现，信号初始化为 0，就代表着是同步信号量，它可以保证进程 A 应在进程 B 之前执行。

信号

对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。

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

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

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

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

Socket

跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。

1
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 即可；

总结

由于每个进程的用户空间都是独立的，不能相互访问，这时就需要借助内核空间来实现进程间通信，原因很简单，每个进程都是共享一个内核空间。

处理多线程冲突

互斥的概念

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

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

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

另外，说一下互斥也并不是只针对多线程。在多进程竞争共享资源的时候，也同样是可以使用互斥的方式来避免资源竞争造成的资源混乱。

同步

我们都知道在多线程里，每个线程并不一定是顺序执行的，它们基本是以各自独立的、不可预知的速度向前推进，但有时候我们又希望多个线程能密切合作，以实现一个共同的任务。

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

注意，同步与互斥是两种不同的概念：

  • 同步就好比：「操作 A 应在操作 B 之前执行」，「操作 C 必须在操作 A 和操作 B 都完成之后才能执行」等；
  • 互斥就好比：「操作 A 和操作 B 不能在同一时刻执行」；

实现

在进程/线程并发执行的过程中，进程/线程之间存在协作的关系，例如有互斥、同步的关系。

为了实现进程/线程间正确的协作，操作系统必须提供实现进程协作的措施和方法，主要的方法有两种：

  • 锁：加锁、解锁操作；
  • 信号量：P、V 操作；

在说明「忙等待锁」的实现之前，先介绍现代 CPU 体系结构提供的特殊原子操作指令 —— 测试和置位（*Test-and-Set*）指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr;
    *old_ptr = new;
    return old;
}

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1);
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

很明显，当获取不到锁时，线程就会一直 while 循环，不做任何事情，所以就被称为「忙等待锁」，也被称为自旋锁（*spin lock*）。

这很消耗时间，造成 CPU 空转。

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

1
2
3
4
type struct lock_t {
    int flag;
    queue_t *q; // 等待队列
} lock_t;

信号量

通常信号量表示资源的数量，对应的变量是一个整型（sem）变量。

另外，还有两个原子操作的系统调用函数来控制信号量的，分别是：

  • P 操作：将 sem 减 1，相减后，如果 sem < 0，则进程/线程进入阻塞等待，否则继续，表明 P 操作可能会阻塞；
  • V 操作：将 sem 加 1，相加后，如果 sem <= 0，唤醒一个等待中的进程/线程，表明 V 操作不会阻塞；

PV 操作的函数是由操作系统管理和实现的，所以操作系统已经使得执行 PV 函数时是具有原子性的。

信号量不仅可以实现临界区的互斥访问控制，还可以线程间的事件同步。

我们先来说说如何使用信号量实现临界区的互斥访问。

为每类共享资源设置一个信号量 s，其初值为 1，表示该临界资源未被占用。

只要把进入临界区的操作置于 P(s) 和 V(s) 之间，即可实现进程/线程互斥：

使用信号量实现事件同步。

同步的方式是设置一个信号量，其初值为 0

生产者消费者问题

使用三个信号量解决这个问题。

哲学家就餐问题

……

看晕了，但其实也没啥用。

如何避免死锁

锁

互斥锁与自旋锁

一个进程最多可以创建多少线程。