进程与线程

# 进程与线程

操作系统中最核心的概念是进程。

进程时系统资源分配的基本单位（可以看成是资源的容器），线程是调度的基本单位。

# 进程

在多道程序设计设计系统中，CPU由一个进程快速切换至另一个进程，使每个进程各运行几十或几百毫秒。严格地说，在某一个瞬间，CPU只能运行一个进程。

# 进程模型

进程：一个进程就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值。

从概念上说，每个进程拥有它自己的虚拟CPU。实际上真正的CPU在各进程之间来回切换。

# 进程的创建

4种主要事件会导致进程的创建：

系统初始化。
正在运行的程序执行了创建进程的系统调用。
用户请求创建一个进程。
一个批处理作业的初始化。

启动操作系统时，通常会创建若干个进程。有些是前台进程，而有些是后台进程（守护进程）。

守护进程（daemon）：停留在后台处理诸如电子邮件、Web页面、新闻、打印之类活动的进程。通过ps可查看linux的守护进程。

从技术上看，新进程都是由于一个已存在的进程执行了用于创建进程的系统调用而创建的。

子进程与父进程

在UNIX系统中，只有一个系统调用可以用来创建新进程：fork。这个系统调用会创建一个与调用进程相同的的副本。在用于了fork后，这两个进程（父进程和子进程）拥有相同的内存映射、同样的环境字符串和同样的打开文件。这就是全局情形。通常，子进程接着执行execve或一个类似的系统调用，以修改其内存映射并运行一个新的程序。例如，当一个用户在shell中键入命令sort时，shell就创建一个子进程，然后，这个子进程执行sort。之所以要按两步建立进程，是为了fork之后但在execve之前允许该子进程处理其文件描述符，这样可以完全对标准输入文件、标准输出文件和标准错误文件的重定向。

父进程和子进程各自拥有不同的地址空间。在UNIX中，子进程的初始地址空间是父进程的一个副本，但是这涉及两个不同的地址空间，不可写的内存区是共享的。特别地，可写的内存实不可以共享的。

# 进程的终止

引起进程终止的条件：

正常退出（自愿的）。
出错退出（自愿的）。
严重错误（非自愿）。
被其他进程杀死（非自愿）。

在UNIX中通知进程终止的系统调用时exit，Win32的是ExitProcess。

第四种终止进程的原因是，某个进程执行一个系统调用通知操作系统杀死某个其他进程。在UNIX中，这个系统调用是kill。在Win32中对应的函数是TerminateProcess。

# 进程的层次结构

某些系统中，当进程创建了另一个进程后，父进程和子进程就以某种形式继续保持关联。在UNIX中，进程和它的所有子进程以及后裔共同组成一个进程组。

# 进程的状态

进程有三种状态：

运行态（该时刻进程实际占用CPU）。
就绪态（可运行，但因为其他进程正在运行而暂时停止）。
阻塞态（除非某种外部事件发生，否则进程不能运行）。

进程的三种状态之间有四种可能的转换关系，如图：

# 进程的实现

为了实现进程模型，操作系统维护着一张表格（一个结构数组），即进程表（process table）。每个进程占用一个进程表项（进程控制块）。该表项包含了进程的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息，以及其他进程由运行态转换到就绪态或阻塞态时必须保存的信息，从而保证该进程随后能再次启动，就像从未被中断过一样。

典型的进程表表项中的一些字段：

中断向量（interrupt vector）：与每一I/O类关联的是一个称作中断向量的位置（靠近内存底部的固定区域）。它包含中断服务程序的入口地址。假设当一个或多个磁盘中断发生时，用户进程正在运行，则中断硬件将程序计数器、程序状态字、有时还有一个或多个寄存器压入堆栈，计算机随机跳转到中断向量所指示的地址。这些是硬件完成的所有操作，然后软件，特别是中断服务例程即接管一切剩余的工作。

中断处理和调度的过程：

硬件压入堆栈程序计数器。
硬件从中断向量装入新的程序计数器。
汇编语言过程保存寄存器值。
汇编语言过程设置新的堆栈。
C中断服务例程运行（典型地读和缓冲输入）。
调度程序决定一个将运行的进程。
C过程返回至汇编代码。
汇编语言过程开始运行新的当前进程。

# 多道程序设计模型

采用多道程序设计可以提高CPU的利用率。

更好的模型是从概率的角度来看CPU的利用率。假设一个进程等待I/O操作的时间与其停留在内存中时间的比为p。当内存中同时有n个进程时，则所有n个进程都在等待I/O（此时CPU空转）的概率是。CPU的利用率由下面的公式给出：

$利用率$

多道程序设计的道数（degree of multiprogramming）：

# 线程

进程：每个进程有一个地址空间和一个控制线程。
线程：同一个地址空间中运行多个控制线程，这些线程就像分离的进程（共享地址除外）。
进程、线程和协程的大小
- 进程：linux下默认大小10M
- 线程：linux下默认大小8M
- 协程：linux下默认大小1M

# 线程的使用

需要线程的三个理由

共享一个地址空间和所有可用数据。并行实体拥有共享地址空间和所有可用数据的能力，线程不必考虑中断、定时器和上下文切换，而只需考察并行进程。
更轻量，容易创建和撤销。由于线程比进程更轻量，所以它们比进程更容易（即更快）创建，也更容易撤销。在许多系统中，创建一个线程较创建一个进程要快10~100倍。
提升I/O密集型应用性能。若多个线程都是CPU密集型的，那么并不能获得性能上的增强，但是如果存在着大量的计算和大量的I/O处理，拥有多个线程允许这些活动彼此重叠进行，从而会加快应用程序执行的速度。

构造服务器的三种方法

模型	特性
多进程	并行性、阻塞系统调用
单线程进程	无并行性、阻塞系统调用
有限状态机	并行性、非阻塞系统调用、中断

有限状态机：每个计算都有一个被保存的状态，存在一个会发生且使得相关状态发生改变的事件集合，这类设计称为有限状态机（finite-state machine）。

# 经典的线程模型

进程
- 资源分组处理
  - 程序正文和数据
  - 其他资源的地址空间
- 执行
  - 进程拥有一个执行的线程（thread）
每个线程有的属性
- 程序计数器：记录接着要执行哪一条指令
- 寄存器：保存线程当前的工作变量
- 堆栈：记录执行历史，每一个帧保存了一个已调用的但是还没有从中返回的过程
线程共享的内容：同一个进程的内容（除了程序计数器、寄存器、堆栈和状态）。

线程的内容：

每个进程中的内容（线程共享的内容）	每个线程中的内容（线程独立的内容）
地址空间	程序计数器
全局变量	寄存器
打开文件	堆栈
子进程	状态
即将发生的定时器
信号与信号处理器
账户信息

进程和线程的区别：进程用于把资源集中到一起，而线程则是在CPU上被调度执行的实体。

线程的调用：

库函数thread_create创建新线程。所有的线程都是平等的。使用库函数thread_exit退出线程。
thread_yield函数允许线程自动放弃CPU从而让另一个线程允许。

# POSIX线程

为实现可移植的线程程序，IEEE在IEEE标准1003.1c中定义了线程的标准。它定义的线程包叫作pthread。

所有pthread线程都有某些特性。每一个都含有一个标识符、一组寄存器（包括程序计数器）和一组存储在结构中的属性。这些属性包括堆栈大小、调度参数以及其他线程需要的项目。

线程调用	描述	备注
pthread_create	参加一个新线程	跟fork系统调用类似，返回一个线程标识符，该标识符起着PID的作用
pthread_exit	结束调用的线程
pthread_join	等待一个特定的线程退出	一般一个线程在继续运行前需要等待另一个线程完成它的工作并提出。可以用pthread_join来等待。
pthread_yield	释放CPU来运行另外一个线程	一个线程逻辑上没有阻塞，但感觉上它已经运行了足够长时间并且希望给另外一个线程机会去运行。这时可以调用pthread_yield完成这目标。
pthread_attr_init	创建并初始化一个线程的属性结构
pthread_attr_destory	删除一个线程的属性结构

# 在用户空间中实现线程

实现线程包的方式：

在用户空间中实现
在内核中实现
混合实现

用户空间中实现线程

把整个线程包放在用户空间中，内核对线程一无所知。从内核角度考虑，就是按正常的方式管理，即单线程进程。

优点

用户级线程包可以在不支持线程的操作系统上实现。
这样的线程切换至少比陷入内核要快一个数量级，这是使用用户级线程包的极大优点。
线程调度非常快捷：
1. 保存该线程状态的过程和调度程序都只是在本地过程，所以启动它们比进行内核调用效率更高。
2. 不需要陷入内核，不需要上下文切换，也不需要对内存高速缓存进行刷新。
允许每个进程有自己定制的调度算法。
具有较好的可拓展性。

缺点

较难实现阻塞系统调用。
缺页中断问题。如果有一个线程引起页面故障，内核由于不知道有线程存在，通常会把整个进程阻塞直到磁盘I/O完成为止，尽管其他的线程是可以运行的。
如果一个线程开始运行，那么在该进程中的其他线程就不能运行，除非第一个线程自动放弃CPU。
不适用于CPU密集型和极少有阻塞的应用程序。

# 在内核中实现线程

内核线程和用户级线程的区别

内核线程不需要运行时系统，每个进程中也没有线程表。内核中有记录系统中所有线程的线程表。创建和撤销线程都会进行一个系统调用。
内核的线程表保存的线程信息是传统内核所维护的每个单线程进程信息（即进程状态）的子集。
所有能够阻塞线程的调用都以系统调用的形式实现，这与运行时系统过程相比，代价是相当可观的。
由于在内核中创建和撤销线程代价比较大，可将撤销线程改为标志线程为不可运行，在创建新线程时重新启动某个旧的线程。用户级线程没必要这么做。
内核线程不需要任何新的、非阻塞系统调用。
系统调用的代价比较大，所以如果线程的操作（创建、终止等）比较多，就会带来很大的开销。

# 混合实现

使用内核级线程，然后将用户级线程与某些或者全部内核线程多路复用起来。编程人员可以决定有多少个内核级线程和多少个用户级线程彼此多路复用。这一模型带来最大的灵活读。

# 进程间通信

进程间通信（Inter Process Communication， IPC）。进程经常需要与其他进程通信，进程间通信需要以下解决三个问题。

一个进程如何把信息传递给另一个。
确保两个或更多的进程在关键活动中不会出现交叉。例如，在飞机订票系统中的两个进程为不同的客户试图争夺飞机上的最后一个座位。
如何保证正确的顺序。

# 竞争条件

两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件（race condition）。

例如这段代码：

from multiprocessing import Process
import time


def fun(val):
    time.sleep(0.1)
    with open("common.txt", "w") as f:
        f.write(val)


if __name__ == '__main__':
    process = [Process(target=fun, args=(str(x),)) for x in range(2)]
    for p in process:
        p.start()
    for p in process:
        p.join()
    with open("common.txt", "r") as f:
        print("after: ", f.read())

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

同时启动2个进程对文件common.txt进行写数据，在每次执行程序后文件的内容可能都会不一样。

# 临界区

实际上凡涉及共享内存、共享文件以及共享任何资源的情况都会引发与前面竞争条件相似的错误。我们需要互斥（mutual exclusion），即以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。

临界区域（critical region）或临界区（critical section）：我们把共享内存进行访问的程序片段称为临界区域（critical region）或临界区（critical section）。

避免竞争条件，保证使用共享数据的并发进程能够正确和高效的进行协程，需要满足以下4个条件：

任何两个进程不能同时处于其临界区。
不应对CPU的速度和数量做任何假设。
临界区外运行的进程不得阻塞其他进程。
不得使进程无期限等待进去临界区。

# 忙等待的互斥

屏蔽中断：使每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。屏蔽中断后，时钟中断也被屏蔽。
1. 把屏蔽中断的权利交为用户进程是不明智的。
2. 屏蔽中断对于操作系统本身而言是一项很有用的技术，但对于用户进程则不是一种合适的通用互斥机制。
锁变量。
严格轮换法。
1. 连续测试一个变量直到某个值出现为止，称为忙等待（busy waiting）。浪费CPU时间，应避免。
2. 用于忙等待的锁，称为自旋锁（spin lock）。
3. 严格轮换法违反了前面的条件3：临界区之外有进程阻塞。
Peterson解法。
TSL指令。

# 睡眠与唤醒

Peterson解法和TSL或XCHG解法都是正确的，但它们都有忙等待的缺点。

sleep和wakeup：它们在无法进入临界区时被阻塞，而不是忙等待。sleep是一个将引起调用进程阻塞的系统调用，即被挂起，直到另外一个进程将其唤醒。wakeup调用有一个参数，即要被唤醒的进程。

生产者——消费者（producer-consumer）问题。

# 信号量

信号量（semaphore）：信号量是E.W.Dijkstra在1965年提出的一种方法，它使用一个整数变量来累计唤醒次数，供以后使用。一个信号量的取值可以为0（表示没有保存下来的唤醒操作，即阻塞）或者为正值（表示有一个或多个唤醒操作）。

信号量有两种操作：down和up（分别为一般化后的sleep和wakeup）。

检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成。保证一旦一个信号量操作开始，则在该操作完成或阻塞之前，其他进程不允许访问该信号量。所谓原子操作，是指一组相关联的操作要么都不间断地执行，要么都不执行。

# 互斥量

互斥量（mutex）：简化版的信号量，去除了信号量的计数能力。

互斥量仅仅是用于管理共享资源或一小段代码。由于互斥量在实现时既容易又有效，这使得互斥量在实现用户空间线程包时非常有用。

互斥量是一个开源处于两态之一的变量**：解锁**和加锁。0表示解锁，其他所有的值则表示加锁。

mutex_lock：加锁。调用mutex_lock时，如果该互斥量当前是解锁的（即临界区可用），此调用成功，调用线程可以自由进入该临界区。如果该互斥量以及加锁，调用线程被阻塞，直到临界区中的线程完成并调用mutex_unlock。如果多线程被阻塞在该互斥量上，将随机选择一个线程并允许它获得锁。
mutex_unlock：解锁。

enter_region和mutex_lock的差别：

当enter_region进入临界区失败时，它始终重复测试锁（忙等待）。实际上，由于时钟超时的作用，会调度其他进程运行。
在（用户）线程中，情形有所不同，因为没有时钟停止运行时间过长的线程。结果是通过忙等待的方式来试图获得锁的线程将永远循环下去，绝不会得到锁，因为这个运行的线程不会让其他线程运行从而释放锁。
mutext_lock取锁失败时，它调用thread_yield将CPU放弃给另一个线程。这样，就没有忙等待。

由于thread_yield只是在用户空间中对线程调度程序的一个调用，所以它的运行非常快捷。这样，mutex_lock和mutex_unlock都不需要任何内核调用。

快速用户区互斥量futex

futex是Linux的一个特性，它实现了基本的锁（很像互斥锁），但避免了陷入内核，除非它真的不得不这样做。

一个futex包含两个部分：一个内核服务和一个用户库。内核服务提供一个等待队列，它允许多个进程在一个锁上等待，在没有竞争条件时，futex完全在用户空间工作。

pthread中的互斥量

pthread提供许多可以用来同步线程的函数。其基本机制是使用一个可以被锁定和解锁的互斥量来保护每个临界区。

# 管程

信号量和互斥量容易出现死锁（deal lock）。为了更易于编写正确的程序，Brinch Hansen（1973）和Hoare（1974）提出了一种高级同步原语，称为管程（monitor）。

一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。管程有一个很重要的特性，即任一时刻管程中只能有一个活跃进程，这一特性使管程有效地完成互斥。

# 消息传递

上面提到的其他的方法就是消息传递（message passing）。这种进程间通信的方法使用两条原语send和receive，它们像信号量而不像管程，是系统调用也不是语言成分。

消息传递系统的设计要点。
1. 确认（acknowledge）号：每天原始信息嵌入一个连续的序号。
2. 身份认证（authentication）。
用消息传递解决生产者——消费者问题。

# 避免锁：读 - 复制 - 更新

https://lwn.net/Articles/262464/

最快的锁是没有锁。在没有锁的情况下对共享数据结构的并发读写进行访问。

在某些情况下，可以允许写操作来更新数据结构，即便还有其他的进程正在使用它。巧门在于确保每个读操作要么读取旧的数据版本，要么读取新的数据版本，但绝不能是新旧数据的一些奇怪组合。

RCU（Read-Copy-Update，读-复制-更新），是基于其原理命名的。RCU并不是新的锁机制，Linux社区关于RCU的经典文档位于https://www.kernel.org/doc/ols/2001/read-copy.pdf，Linux内核源代码Documentation/RCU/也包含了RCU的一些讲解。

不同于自旋锁，使用RCU的读端没有锁、内存屏障、原子指令类的开销，几乎可以认为是直接读（只是简单地标明读开始和读结束），而RCU的写执行单元在访问它的共享资源前首先复制一个副本，然后对副本进行修改，最后使用一个回调机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据，这个时机就是所有引用该数据的CPU都退出对共享数据读操作的时候。等待适当时机的这一时期称为宽限期（grace period）。

# 调度

当内核管理线程的时候，调度经常是按线程级别的，与线程所属的进程基本或根本没有管理。

# 调度简介

进程切换的代价是比较高的：

1、首先用户态必须切换到内核态；

2、然后要保存当前进程的状态，包括在进程表中存储寄存器值以便以后重新装载；

3、接着，通过运行调度算法选定一个新进程；

4、之后，应该将新进程的内存映像重新装入MMU；

5、最后新进程开始运行。

除此之外，进程切换还要使整个内存高度缓存失效，强迫缓存从内存中动态重新装入两次（进入内核一次，离开内核一次）。

# 进程行为

1、计算密集型（compute-bound）

2、I/O密集型（I/O-bound）

# 何时调度

在创建一个新进程之后，需要决定运行父进程还是运行子进程。
在一个进程退出时必须做出调度决策。
当一个进程阻塞在I/O和信号量或由于其他原因阻塞时，必须选择另外一个进程运行。
在一个I/O中断发生时，必须做出调度决策。

# 调度算法分类

根据如何处理时钟中断，可以把调度算法分为两类：

非抢占式
抢占式

# 调度算法的目标

所有系统
- 公平——给每个进程公平的CPU份额
- 策略强制执行——保证规定的策略被执行
- 平衡——保持系统的所有部分都忙碌
批处理系统
- 吞吐量——每小时最大作业数
- 周转时间——从提交到终止间的最小时间
- CPU利用率——保持CPU始终忙碌
交互式系统
- 响应时间——快速响应请求
- 均衡性——满足用户的期望
实时系统
- 满足截止时间——避免丢失数据
- 可预测性——在多媒体系统中避免品质降低

# 批处理系统中的调度

先来先服务
最短作业优先
最短剩余时间优先

# 交互式系统中的调度

轮转调度
1. 每个进程被分配一个时间段，称为时间片（quantum），即允许该进程在该时间段中运行。
2. 时间片设得太短会导致过多的进程切换，降低了CPU效率；而设得太长又可能引起对短的交互请求的响应时间变长。将时间片设为20~50ms通常是一个比较合理的折中。
优先级调度
多级队列
最短进程优先
保证调度
彩票调度
公平分享调度

# 实时系统中的调度

实时系统是一种时间起着主导作用的系统。

实时系统通常可以分为硬实时（hard read time）和软实时（soft real time）。前者的含义是必须满足绝对的截止时间，后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。

实时系统中的事件可以按照响应方式进一步分类为周期性（以规则的时间间隔发生）事件和非周期性（发生时间不可预知）事件。

# 策略和机制

将调度机制（scheduling mechanism）与调度策略（scheduling policy）分离，也就是将调度算法以某种形式参数化，而参数可以有用户进程填写。

例如数据库，调度机制位于内核，而调度策略则由用户进程决定。策略与机制分离是一种关键性思路。

# 线程调度

当若干进程都有多个线程时，就存在两个层次的并行：进程和线程。

用户级线程：用户级线程的调度算法由运行时系统（用户层）决定。由于内核并不知道有线程存在，所以内核还是和以前一样地操作，选取一个进程进行调度。
内核级线程：内核级线程的调度算法由内核实现。内核选择一个特定的线程运行，它不用考虑该线程属于哪个进程，不过有必要的话可以这样做。

用户级线程和内核级线程之间的差别在于性能：用户级线程的线程切换需要少量的机器指令，而内核级线程需要完整的上下文切换，修改内存映射，使高速缓存失效，这导致了若干数量级的延迟。另一方面，在使用内核级线程时，一旦线程阻塞在I/O上就不需要像在用户级线程中那样将整个进程挂起。

#操作系统

上次更新: 2024/05/29, 14:25:22

← 操作系统框架内存管理→