程序、进程、线程

概述

• 程序是静态的代码集合
• 进程是程序在执行过程中的实例，是操作系统分配资源的基本单位
• 线程是进程内的执行单位，用于实现并发执行和共享资源

程序（Program）

程序是指一组指令的集合，它是静态的、存储在磁盘或其他存储介质上的代码。程序本身并没有在计算机上执行，只有在被加载到内存并由操作系统调度执行时，才成为一个活动的实体。

进程&线程

	进程	线程
作用	资源分配的单位、程序在执行过程中的实例。当程序被加载到内存中并开始执行时，操作系统会为该程序创建一个进程，分配给它所需的内存、CPU时间和其他系统资源。	线程是CPU调度的d进程内的执行单位，用于实现并发执行和共享资源
代码基础	共享，不同的进程可以使用相同的程序代码作为基础，即它们可能是从同一个可执行文件加载的	共享
内存空间	独立，每个进程都有自己独立的内存空间，包括代码、数据和堆栈。进程之间的数据不会直接通信和共享数据，除非它们显式地使用进程间通信（IPC） 机制（管道、共享内存、消息队列等）	共享，线程在同一个进程内共享相同的地址空间，可以直接访问和修改进程中的共享数据（一个线程可以读、写、清除另一个线程的堆栈），通信可以直接通过共享内存进行
资源分配	独立，例如文件描述符、打开的文件、网络连接等。一个进程无法直接访问或操作另一个进程的资源	共享，包括代码段、数据段、打开的文件、网络连接、信号处理程序等
执行环境	独立，例如PC和栈。一个进程的控制流程不会直接影响其他进程	独立
控制和状态	独立，例如进程ID、父进程ID、优先级等。这些信息用于操作系统调度和管理进程，使它们能够独立运行和被管理	独立
异常和信号处理	独立	独立
区别	独立性：进程是独立的执行实体，每个进程有自己独立的地址空间和资源。进程之间相互隔离，一个进程的崩溃不会直接影响其他进程	线程是进程内的执行单位，多个线程共享同一个进程的地址空间和资源，它们之间相互依赖，一个线程的崩溃可能会导致整个进程的崩溃
区别	错误隔离：进程之间相互隔离，一个进程的错误不会直接影响其他进程	线程共享同一个进程的资源，一个线程的错误可能会影响其他线程
区别	创建和切换开销：较大，需要操作系统进行地址空间和资源的切换	较小，因为它们共享进程的地址空间和资源，仅需要切换栈和寄存器等少量状态。
区别	并发性和共享：并发执行需要依靠进程间通信（IPC）机制，共享数据的开销较大	线程之间可以并发执行，共享进程的资源，实现更高的并发性
区别	调度粒度：进程是操作系统分配资源的基本单位，调度粒度较粗	线程是操作系统调度的基本单位，因为线程的切换开销较小，所以调度粒度较细
联系	执行单元：进程和线程都是执行代码的实体。进程是程序的执行实例，而线程是进程内的执行单位。
联系	共享资源：进程和线程都可以共享相同的内存资源，包括代码段、数据段和堆栈等。这使得它们能够相互通信和共享数据，提高程序的效率和灵活性。
联系	调度和管理：操作系统负责进程和线程的调度和管理。它们都可以被操作系统挂起、恢复和调度执行，以满足系统的需求。
补充	由于线程共享相同的地址空间，线程之间的共享数据访问需要进行适当的同步和互斥操作，以避免竞态条件和数据一致性问题。同步机制如互斥锁、信号量、条件变量等可以用于线程间的协调和数据保护	线程局部存储：独立，每个线程可以有自己的线程局部存储（Thread Local Storage，TLS），允许线程在共享内存的同时拥有自己的独立存储空间，用于存储线程特定的数据。

进程

关键抽象

一个独立的逻辑控制流，提供一个假象，好像程序独占地使用处理器

• 并发：执行时间上重叠
• 并行：并发地运行在不同的处理器核
  

一个私有的地址空间，提供一个假象，好像程序独占地使用内存系统

内核模式

“以管理员身份运行”和“内核模式”在不同的层次上进行授权和权限管理。

• “以管理员身份运行”：用户对于操作系统资源的权限设置，授权用户可以执行特权操作。
• “内核模式”：操作系统本身的运行模式，只有操作系统内核及其相关组件才能运行在这个模式下，并具有对系统资源的直接访问能力。

进程的创建：fork()函数

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

"fork"作为创建子进程的意思，是因为它描述了父进程在创建子进程时的行为，类似于一个进程在某个时间点分叉成两个独立的进程。

• fork调用一次，返回两次
• 并发执行：顺序不一定
• 父进程中，fork返回子进程的PID；子进程中，返回0
• 地址空间相同但独立：任何改变都是独立的，不会反映在另一个进程的内存中。
• 共享文件

fork函数将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。当fork在新进程中返回时，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

进程的状态

进程的加载和运行：execve()函数

在当前进程中加载并运行其他可执行文件。若成功则不返回，若失败则返回-1

int execve(const char *filename, char *const argv[], char *const envp[]);

• 删除已存在的用户区域
• 映射私有区域（写时复制）
• 映射共享区域（动态链接）
• 设置PC指向代码区域的入口点

fork和execve的区别

• fork在新的子进程运行相同的程序，子进程是父进程的复制品
• execve加载并运行新的程序，覆盖当前进程的地址空间，但不创建新进程，PID不变

进程的上下文切换

只发生在内核态，包含虚拟内存、栈、全局变量等用户空间的资源，也包括内核堆栈、寄存器等内核空间的资源

进程的终止

• 正常退出(自愿)
• 出错退出(自愿)
• 严重错误(非自愿)
• 被其他进程杀死(非自愿)

父进程、子进程

继承的资源副本：

• 内存空间：子进程从父进程继承了相同的代码段、数据段和堆栈，使得子进程能够执行相同的程序代码。

• 文件描述符：子进程可以直接访问和操作父进程打开的文件，包括读取、写入和关闭文件。

• 环境变量：包括环境变量的名称和值，子进程可以直接使用这些环境变量。

• 控制信息：例如进程组ID、会话ID等。

• 信号处理程序：子进程会继承父进程对信号的处理方式，包括忽略、捕捉或执行默认操作。

• 执行上下文的属性：例如PC、寄存器状态和进程状态等。这些属性使得子进程能够从父进程中继续执行，并且能够在父进程终止后继续独立执行。

需要注意的是，虽然子进程从父进程那里继承了这些资源，但子进程会创建它们自己的独立副本，这样子进程对这些资源的修改不会影响其他进程。子进程的资源副本与父进程的资源是相互独立的。

回收子进程

父进程等待子进程的终止并获取其退出状态

waitpid()函数

waitpid()函数是一个用于等待子进程状态改变的系统调用函数。它用于在父进程中等待子进程的终止或其他状态变化，并获取子进程的退出状态。

#include <sys/types.h>
#include <sys/wait.h>pid_t waitpid(pid_t pid, int *status, int options);

参数解释

pid：指定要等待的子进程的进程ID。取值可以是以下几种：

<-1	等待进程组ID为pid绝对值的任何子进程。
-1	等待任何子进程，相当于wait函数。
0	等待与调用进程在同一进程组的任何子进程。

options：指定等待子进程的行为选项，可以是以下值的位掩码或其组合：

默认行为	等到有子进程终止
WNOHANG	设置为非阻塞模式。如果指定的子进程还没有终止或改变状态，waitpid立即返回0，而不阻塞父进程。如果子进程已经终止或改变状态，则返回子进程的进程ID
WUNTRACED	等待被暂停的子进程。如果子进程被暂停，则waitpid返回子进程的进程ID
WCONTINUED	等待被继续执行的子进程。如果子进程被继续执行，则waitpid返回子进程的进程ID

status：用于存储子进程的退出状态或其他信息的整型指针。子进程的状态信息可以通过该指针来获取。

WIFCONTINUED(status)	检查子进程是否被继续执行。如果返回非零值，则表示子进程被继续执行
WIFEXITED(status)	检查子进程是否正常退出。如果返回非零值，则表示子进程正常退出
WEXITSTATUS(status)	获取子进程的退出状态值。仅当WIFEXITED返回非零值时才有意义
WIFSIGNALED(status)	如果返回非零值，则表示子进程被信号终止
WTERMSIG(status)	获取终止子进程的信号编号。仅当WIFSIGNALED返回非零值时才有意义
WIFSIGNALED(status)	检查子进程是否被信号终止。如果返回非零值，则表示子进程被信号终止
WIFSTOPPED(status)	检查子进程是否被暂停。如果返回非零值，则表示子进程被暂停

错误条件

• 若调用进程没有子进程，则waitpid返回1，并且设置errno为ECHILD
• 若waitpid函数被一个信号中断，则waitpid返回1， 并设置errno为EINTR

wait函数

wait( &status ) 是 waitpid( -1 , &status , 0 ) 的简化

#include <sys/types.h>
#include <sys/wait.h>pid_t wait(int *status);

线程

线程的种类

• 用户线程：对OS透明，切换速度快
• 内核线程：充分利用多核处理器的并行性
• 轻量级线程：由线程库在用户空间实现和管理，而底层的调度和同步操作由操作系统的内核线程完成

线程自己的堆栈

每当创建一个新线程时，操作系统会为该线程分配一段堆栈空间。这个堆栈空间是线程独有的，不会被其他线程共享。每个线程都有一个指向当前堆栈顶部的指针，该指针称为堆栈指针（Stack Pointer）或栈顶指针（SP）。

线程的堆栈用于存储函数调用的上下文信息，包括函数的参数、局部变量、返回地址、调用的函数中间结果、函数调用信息和临时数据等。当线程执行函数调用时，相关的信息会被压入堆栈；当函数返回时，这些信息会从堆栈中弹出。

• 线程自己的堆栈
  每个线程都有自己独立的堆栈空间，用于存储线程的局部变量、函数调用信息和临时数据等。线程的堆栈是用于支持函数调用和返回的数据结构，用于维护函数调用的上下文。每个线程的堆栈是独立的，不会被其他线程共享。线程的堆栈空间有限，当线程使用堆栈空间超过其限制时，会发生堆栈溢出（stack overflow）错误。

• 线程局部存储
  线程局部存储是一种机制，允许每个线程拥有自己独立的变量副本，这些变量只能被当前线程访问。线程局部存储可以通过关键字或函数来声明，将变量标记为线程局部的。每个线程都有自己的变量副本，不同线程之间的变量相互独立，互不干扰。线程局部存储适用于那些需要在不同线程之间保持独立状态的变量，例如线程特定的配置、线程私有的缓存等。

弹出式线程

“弹出式线程”（Pop-up Thread）是一种特殊类型的线程，也称为"轻量级线程"或"绿色线程"。它是在用户空间中实现的线程，而非由操作系统内核管理的线程。

传统的线程模型中，线程的创建、销毁和切换都由操作系统内核负责管理，这种线程被称为内核线程（Kernel Thread）。而弹出式线程是在应用程序级别实现的，由应用程序自己管理线程的创建、销毁和调度，而不依赖于操作系统的支持。

• 用户空间线程：弹出式线程是在应用程序的用户空间中创建和管理的，不依赖于操作系统的线程管理机制。它的创建和切换操作是由应用程序自己实现的，不需要进行系统调用。

• 轻量级：由于弹出式线程在用户空间中运行，它们相对于内核线程来说更轻量级。创建和销毁弹出式线程的开销较小，线程切换也更快速。

• 多对一模型：弹出式线程通常采用多对一的线程模型，即多个弹出式线程映射到一个内核线程。这意味着所有的弹出式线程共享一个内核线程，它们在用户空间中轮流执行，由应用程序负责线程的调度。

• 非抢占式：弹出式线程通常是非抢占式的，也就是说，在没有显式让出CPU的情况下，弹出式线程会一直执行，直到自己主动释放CPU控制权。

弹出式线程的优势在于它们对线程的创建和调度有更高的灵活性和控制权。应用程序可以根据自身的需求自由创建和管理弹出式线程，更好地适应特定的并发编程模型和算法。然而，弹出式线程也存在一些限制，例如无法充分利用多核处理器的并行性，以及由于线程调度由应用程序负责，可能会导致线程饥饿和不公平性等问题。因此，在选择使用弹出式线程时，需要根据具体情况进行评估和权衡。

进程间通信（IPC）

Inter Process Communication

三个问题

• 传递信息
• 关键活动中不交叉
• 正确的顺序

解决竞争的四个条件

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

竞争：进程读写某些共享数据，最后的结果取决于进程运行的精确时序
互斥：阻止多个进程同时读写共享的数据
临界区：对共享内存进行访问的程序片段

忙等待的互斥

忙等待：连续测试一个变量，直到某个值出现
自旋锁：用于忙等待的锁

• 屏蔽中断：CPU只有在发生时钟中断或其他中断时才会进程切换
• 锁变量：软件
• 严格轮换法
• TSL指令(Test and set lock)：CPU锁住内存总线，以禁止其他CPU在本指令结束之前访问内存

信号量

两种原子操作：

• P操作（也称为down，等待操作或减操作）：P操作用于获取资源或进入临界区。它的作用是将信号量的计数器减一，表示获取了一个资源或进入了临界区。如果信号量的计数器为0，表示资源已经全部被占用，此时执行P操作的线程或进程会被阻塞，进入等待状态，直到有资源可用为止。

P(S):S = S - 1if S < 0:阻塞线程或进程

• V操作（也称为up，释放操作或增操作）：V操作用于释放资源或离开临界区。它的作用是将信号量的计数器加一，表示释放了一个资源或离开了临界区。如果有其他线程或进程正在等待该信号量，执行V操作会唤醒其中一个等待者，使其可以继续执行。

V(S):S = S + 1if S <= 0:唤醒等待的线程或进程

• 信号量S的初始值为0
• 若为1，表示没有线程进入临界区
• 若为0，表示有一个线程进入临界区：
• 若为-1，表示一个线程进入临界区，另一个线程等待进入。

互斥量

futex和pthread

• futex（Fast Userspace Mutex）是一种内核级的轻量级同步原语，可以作为底层机制来支持这些高级同步原语的实现
• pthread（POSIX Threads）是一套标准的线程API库，提供了一系列的线程操作函数，包括线程的创建、终止、同步和互斥等功能，以及丰富的线程同步原语和工具，例如互斥锁、条件变量、信号量
• 它们可以结合使用，以实现更高效和灵活的线程同步和管理。

条件变量

条件变量的主要目的是允许一个线程等待某个特定条件的发生，而不是忙等待。当某个线程发现条件不满足时，它可以进入等待状态，暂时释放互斥锁，并等待其他线程通过条件变量的通知来唤醒它。

条件变量的使用涉及以下三个主要操作：

• 等待：当线程发现条件不满足时，它可以调用条件变量的等待操作，进入等待状态。等待操作会释放相关的互斥锁，使其他线程可以获取该锁并修改共享资源。线程会一直等待，直到被其他线程通过条件变量的通知唤醒。

• 通知：线程可以通过条件变量的通知操作唤醒一个或多个等待的线程。通知操作会重新获取相关的互斥锁，然后选择性地唤醒一个或多个等待线程，使它们从等待状态转变为可运行状态。

• 广播：与通知操作类似，广播操作也是用于唤醒等待的线程，但它会唤醒所有等待线程，而不仅仅是一个或少数几个。

条件变量的典型用法是结合互斥锁使用，通过互斥锁来保护共享资源的访问，并使用条件变量来控制线程的等待和唤醒。线程在等待条件变量时会释放互斥锁，从而允许其他线程访问共享资源。当满足特定条件时，通过条件变量的通知操作来唤醒等待的线程，使它们可以继续执行。

互斥量和互斥信号量

互斥量（Mutex）：互斥量是一种同步原语，用于保护共享资源的访问。有两种状态：锁定状态和非锁定状态。当一个线程需要访问共享资源时，它会先尝试获取互斥量的锁，如果锁是可用的，则线程获得锁，执行对共享资源的操作，并在完成后释放锁，使其他线程能够获得锁并执行操作。如果锁已被其他线程占用，线程将被阻塞，直到锁可用为止。

互斥信号量（Mutex Semaphore）：互斥信号量是一种特殊的信号量，也用于实现对共享资源的互斥访问。它是一种二进制信号量，只能取0或1两个值。当一个线程需要访问共享资源时，它会尝试获取互斥信号量的值，如果值为1，表示资源未被占用，线程可以继续执行并将互斥信号量的值置为0，表示资源已被占用。如果值为0，表示资源已被其他线程占用，线程将被阻塞，直到互斥信号量的值为1。当线程完成对共享资源的访问后，会释放互斥信号量，将其值置为1，表示资源可用。

管程

• 封装性：管程将共享数据和操作该数据的方法封装在一起，通过定义在管程中的过程（也称为方法或函数）来实现线程间的同步和互斥。

• 互斥性：管程通过提供互斥锁（Mutex）来保护共享资源的访问，确保同一时间只有一个线程可以操作数据。任意时刻，管程中只有一个活跃进程

• 支持条件变量

在管程中，共享资源的访问和操作被限制在管程内的过程中，其他线程必须通过调用管程内的过程来访问共享资源，从而保证了线程间的同步和互斥。管程内的过程可以操作共享数据，获取互斥锁，等待条件变量，发出通知等。

• 等待（wait）操作：在条件变量上等待，同时释放当前的互斥锁。该线程会进入等待队列，并等待被其他线程通过通知操作唤醒。
• 通知（signal）操作：选择性地唤醒一个或多个等待在条件变量上的线程。被唤醒的线程会重新尝试获取互斥锁，从而继续执行。

消息传递

• 发送操作（send）：通常会阻塞发送方，直到消息被接收方接收或处理。
• 接收操作（receive）：通常会阻塞接收方，直到有发送方发送消息到达。

通知传递的特点包括：

• 异步性：发送方和接收方可以独立进行操作，它们不需要同时存在或执行。
• 有界缓冲区：在某些情况下，发送方和接收方之间可以使用有限大小的缓冲区来存储消息，以避免阻塞或数据丢失的问题。
• 顺序性：通知传递的消息通常按照发送的顺序进行处理，保证消息的有序性。

屏障

屏障的主要特点包括：

• 同步点：屏障创建了一个同步点，所有线程或进程在此点前都必须等待，直到所有参与方都到达屏障。
• 阻塞等待：线程或进程在达到屏障时会被阻塞，直到所有参与方都到达屏障。
• 继续执行：一旦所有参与方都到达屏障，将被释放，并可以继续执行后续操作。
• 循环使用：屏障通常是可重复使用的，即在所有参与方到达屏障后，它可以被重置并再次使用。

读-复制-更新（RCU）

RCU的核心思想是并发编程，不需要显式的锁或同步机制。

• 读（Read）：多个线程可以并发地读取共享数据，无需加锁。读操作不会对其他读操作或写操作造成干扰。

• 复制（Copy）：当需要对共享数据进行更新时，RCU采用一种延迟策略。首先，对共享数据进行复制，形成一个副本。这样，读操作可以继续在原始数据上进行，而写操作则在副本上进行。

• 更新（Update）：在副本上执行更新操作，使得新的数据状态生效。一旦更新完成，旧版本的数据将不再使用。

RCU的关键机制是在复制和更新过程中保证读操作的一致性。

• 复制过程使用一种类似于写时复制（Copy-on-Write）的技术，确保读操作不会受到写操作的干扰。
• 更新操作通常采用一种延迟策略，等待所有活跃的读操作完成后再进行。

构造并发程序

基于进程

基于进程的并发编程是一种利用多个进程同时执行来实现并发性的编程方法。每个进程都是独立的执行单元，拥有自己的虚拟地址空间和系统资源。在基于进程的并发编程中，我们可以通过创建多个进程并使它们并行执行来实现任务的并发处理。

• 在父进程中接受客户端连接请求，创建新的子进程提供服务
• 共享文件表，但不共享用户地址空间

基于I/O多路复用

基于I/O多路复用的并发编程是一种利用单个进程同时处理多个I/O事件的编程方法。通过使用I/O多路复用机制，程序可以同时监听多个文件描述符（如套接字、管道、文件等）的可读或可写状态，从而实现并发处理多个I/O操作，而无需创建多个进程或线程。

• 逻辑流被模型化为状态机，数据到达文件描述符后，主程序显式地从一个状态转换到另一个
• 每个逻辑流都能访问该进程的全部地址空间

基于线程

基于线程的并发编程是一种利用多个线程同时执行来实现并发性的编程方法。线程是轻量级的执行单元，运行在同一个进程的上下文中，并共享同一个地址空间和系统资源。在基于线程的并发编程中，可以通过创建和管理多个线程来实现任务的并发处理。

• 像进程流一样由内核调度，像I/O多路复用一样共享同一个地址空间

死锁

发生死锁的四个同时满足的条件

• 互斥条件：多个线程不能同时使用同一个资源
• 持有并等待条件
• 不可剥夺条件
• 环路等待条件

互斥锁、自旋锁

互斥锁（Mutex Lock）：一种同步原语，用于保护共享资源的访问。

• 如果锁已被其他线程占用，线程将被阻塞，直到锁可用为止。
• 互斥锁提供了一种阻塞调度的机制，当线程无法获取锁时会进入睡眠状态，不会消耗CPU资源。
• 加锁失败时，从用户态陷入内核态，两次线程上下文切换（休眠和唤醒）。
• 互斥锁适用于共享资源访问时间较长的情况。

自旋锁（Spin Lock）：一种轻量级的锁，它采用忙等待的方式尝试获取锁，而不是进入睡眠状态。

• 如果锁已被其他线程占用，线程会循环忙等待，不断检查锁是否可用。
• 自旋锁适用于共享资源访问时间较短的情况，因为在忙等待的过程中，线程会持续占用CPU资源，造成一定的性能开销。