第四章

基本概念

进程

• 正在执行的程序，进程执行必须按顺序进行
• 当一个可执行文件加载到内存中时，程序变成进程
• 一个程序可以对应多个进程：同一个可执行程序可以被多次运行，每次运行都会形成一个独立进程
• 例如可以同时打开两个同样的浏览器窗口，或多次运行同一个 .exe/命令，它们的代码可以相同，但进程拥有各自独立的 PCB、地址空间和运行状态

进程由多部分构成

• 程序代码，也称为文本段
• 当前活动，包括 PC、处理器寄存器
  • PC（程序计数器）记录下一条将要执行的指令地址
  • 处理器寄存器用于暂存运行时的关键信息，如操作数、运算结果、栈顶位置、程序状态字等
  • 发生进程切换时，操作系统需要保存和恢复这些寄存器的值，否则进程无法从断点处继续正确执行
• 包含临时数据的堆栈
  • 函数参数、返回地址、局部变量
• 包含全局变量的数据部分
• 包含在Runtime动态分配的内存的堆

进程的状态

五状态进程模型

• new（新建）
  • 进程刚刚被创建出来，但还没有真正进入可运行队列。这时操作系统正在为它分配必要资源，比如建立 PCB、分配地址空间等。
• ready（就绪）
  • 程序已具备运行条件，只差CPU。即程序、数据、资源都基本到位，但此刻CPU正在给别的进程用，它只能在就绪队列里等调度
• running（运行）
  • 进程真正占用了 CPU，正在执行指令。一个单核 CPU 在某一时刻通常只能有一个 running 进程。
• waiting（阻塞/等待）
  • 进程暂时不能继续运行，不是因为缺CPU（与ready区分），而是因为它在等某个事件。
  • 典型为等 I/O 完成、等键盘输入、等磁盘读写、等某个信号或资源
  • 比如进程->文件读写->等待
• terminated（终止）
  • 进程执行结束，或者被系统撤销了。此时它不再参与调度，系统会回收它占用的资源。
• 典型流程：new → ready → running → waiting → ready → running → terminated
• ready vs waiting
  • ready：已经能运行了，缺的是 CPU
  • waiting：连运行条件都还没满足，缺的是某个事件

挂起

• 进程被挂起值的是被移出内存。除非代理程序显式地命令系统进行状态轮换，否则该进程无法从这一状态转移
• 交换分区：用来处理进程的交换
• 就绪：在内存里，等 CPU
• 阻塞：在内存里，等事件
• 挂起就绪：已经具备运行条件，但不在内存里
• 挂起阻塞：本来就在等事件，而且还被换出内存
• 被挂起的原因：
  • Swapping（换出）：为了腾出足够的主存空间，把某些进程挂起并换到外存中
  • Other OS reason（其他操作系统原因）：操作系统因为管理需要，主动把某个进程挂起。比如它是后台进程、实用程序进程、暂时不需要、可能引发问题、需要暂停检查
  • Interactive user request（交互式用户请求）：用户主动要求挂起程序，比如调试程序时暂停执行、实用某种资源时先把程序停住、手动暂停某个任务
  • Timing（定时需要）：有些进程是周期性执行的，不需要一直运行。比如系统监控程序、记账程序、定时任务
  • Parent process request（父进程请求）：可能要求挂起某个子进程，目的可能是检查子进程状态、修改子进程、协调多个子进程之间的活动

进程调度

长期、中期、短期调度器

长期调度器

• 也叫作业调度器。其作用是从外存中的后备作业里，挑选一些作业调入内存，建立成进程，进入就绪队列。

• 决定“哪些作业可以进入系统”

• 控制系统中的多道程序度（内存里同时存在多少进程）

• 调度频率低，因为作业进入系统不是特别频繁

• 常见于批处理系统，在分时系统中往往不明显

中期调度器

• 当系统内存紧张，或者某些进程暂时不需要运行时，中期调度器会把它们挂起，释放内存给更急需运行的进程使用。

• 其处理的是已经在内存中的进程，尤其是：暂时阻塞、短时间内不会运行的进程、优先级较低的进程、占用内存较大但当前不急需的进程

• 主要功能是提高内存利用率、缓解内存压力、调整多道程序的“有效数量”、提高系统整体吞吐和响应能力

短期调度器

• 也叫CPU 调度器。它的作用是从内存中的就绪队列里选择一个进程，让它获得 CPU 执行。

• 决定“哪个就绪进程立刻运行”

• 直接影响 CPU 的使用效率和响应速度

• 调度频率很高，几乎每次时钟中断、进程阻塞或时间片用完时都可能发生

• 必须执行得很快

对比

• 调度对象：
  • 长期调度器面对的是后备作业；
  • 短期调度器面对的是就绪进程。
• 调度目的：
  • 长期调度器控制进入内存的进程数量与类型；
  • 短期调度器控制CPU 分配。
• 调度频率：
  • 长期低；短期高。
• 对系统影响：
  • 长期影响系统负载和资源平衡；
  • 短期影响响应速度和吞吐率。

内存表

• 内存表不仅要记录主存（real/main memory，也就是内存条中的实际内存），还要记录辅存中用于虚拟内存的部分。
• 进程的信息不一定始终都在主存中，操作系统可以通过虚拟内存机制或简单的换入换出机制，把进程暂时放在辅存里保存。
• 必须包含：
  • 要记录主存是如何分配给各个进程的。
  • 要记录辅存中的交换区或虚拟内存空间是怎么分配给进程的。
  • 要记录主存或虚拟内存中各个内存块的保护属性。
  • 要记录管理虚拟内存所必需的信息。

IO表

文件表

进程表

• 必须进行维护以管理进程
• 必须直接或间接引用内存、IO和文件
• OS必须能够访问表本身，因此需要进行内存管理
• 通常存放在RAM到的内核区，表中每一项对应一个进程，也就是一个PCB（进程控制块）
• 当系统要创建一个新进程时，会：
  • 在内核空间里申请一个PCB
  • 把这个PCB加入进程表
  • 初始化该进程的各种信息

进程控制块（PCB）

• 内容
  • 进程状态：正在运行、等待等。
  • 程序计数器：下一个执行指令的位置
  • CPU寄存器：所有以进程为中心的寄存器的内容
  • CPU调度信息：优先级、调度队列指针
  • 内存管理信息：分配给进程的内存
  • 记账信息：使用的CPU、启动后经过的 时钟时间、时间限制
  • I/O状态信息：分配给进程的I/O设备、 打开的文件列表
• 不同操作系统程序实例的PCB格式可能不一样
• 进程控制块是操作系统最重要的数据结构
• 每个进程控制块都包含了操作系统所需进程的所有信息
• 困难的不是访问而是维护

• 上图：进程真正运行的程序数据主要在用户空间，而操作系统管理这个进程所用的信息在内核空间的 PCB 中；两者通过系统调用联系起来。

进程调度队列

• 调度队列本质上是：把处于某种相同等待状态的进程组织在一起，方便操作系统统一管理。“按等待原因分类存放”
• 可理解为操作系统为了管理进程状态转换而设置的一组队列。

进程上的操作

相关概念

• 系统必须提供
  • 进程识别
  • 进程创建
  • 程序执行
  • 进程终止
• 一些基础system call
  • getpid()//获取pid
  • fork()//创建
  • exec*()//执行
  • wait()//等待
  • exit()//退出进程

进程创建

• 新的进程不是系统随便生成的，而是由已有进程创建出来
• 创建别人的进程：父进程
• 被创建出来的子进程：子进程
• 父子关系的意义在于：
  • 便于资源继承
  • 便于调度和管理
  • 父进程可以等待子进程结束
  • 子进程退出后，父进程可以回收它的结束信息
• 内核先创建第一个进程 init，init 再创建其他进程，其他进程再继续创建新进程，最终形成整个系统的进程体系，因此构成进程树

• kernel
  

└── init(PID 1) ├── system service A ├── system service B ├── login process │ └── shell │ ├── vim │ ├── gcc │ └── python └── other daemon

- 孤儿进程通常在父进程非预期被kill时出现，子进程还在运行，但父进程已经不存在，它成为孤儿进程
- 孤儿进程通常被`init`收养

### 父子进程之间关系

- 资源共享
  - 父子共享所有资源
  - 子进程共享父进程进程资源的子集
  - 二者不共享任何资源
- 执行
  - 二者同时并发执行
  - 父进程等待直到子进程终止
  - 子进程让父进程先执行？
- 地址空间
  - 子进程是父进程的复制品
  - 子进程加载另一个新程序
- 父子进程都被创建出来后的执行情况是未知的。都执行、都不执行、先后执行等都有可能

### fork()的步骤和内涵

1. 为新进程在进程表中分配一个位置
2. 给子进程分配一个唯一的进程号PID
3. 复制父进程的进程映像（把父进程当前的运行现场复制一份给子进程，**共享内存除外**）
4. 把父进程已打开的文件的计数加一，表示当前多了一个进程在使用这些文件
5. 把子进程设置为就绪态
6. **向父进程返回子进程PID，向子进程返回0**，因为这样方便区分身份，两个进程都能从`fork()`后继续执行
- 注意返回值与PID的关系，**PID 是进程本身的真实编号；fork() 返回值只是创建完成后内核给父子进程的不同“通知结果”——父进程拿到子进程 PID，子进程拿到 0。**
- fork() 前一份执行流，fork() 后两份执行流；父子进程都从 fork() 的下一句开始执行，但返回值不同，因此能区分父子身份。
- ```c
for(int i=0;i<4;i++)
{
    fork();
}//此代码会生成16个进程，包含新创建的15个子进程，一个原来的进程
//本质二叉树，因为fork后裂变为两个进程

• vfork()能够创建一个共享的进程

进程创建之后

内核可执行一下操作之一，作为调度器例程的一部份

• 留在父进程中
• 将控制权转移到子进程
• 将控制权转移到另一个进程

程序的执行

• exec的本质为在当前进程内部，把原来程序整个替换成一个新程序
• 原程序后面的代码不会再执行
• 原程序的变量、内存、寄存器现场会丢掉
• 但进程号、父子关系等“进程身份”会保留

pid_t pid = fork(); if (pid == 0) { exec(…); // 子进程换成另一个程序 }//fork()先复制出一个子进程，exec()让这个子进程去执行新程序

- `fork+exec`的组合的执行顺序是不确定的，取决于谁先调度
- 有一个子进程结束时（不是全部子进程结束），父进程会被唤醒

## 进程终止

- 无论正常或异常退出，都是调用`exit()`来让系统删除它
- 父进程可使用`abort()`调用来终止子进程执行
- 如果父进程已终止，则所有子进程也必须终止
- 当执行到`wait()`时，其之后的语句顺序才可确定，在此之前的代码是并行执行的，因此无法确定顺序（父子进程的例子）
### 僵尸进程

子进程在调用 exit() 并终止后，如果父进程尚未调用 wait 类函数回收它，就会立刻变成僵尸进程；直到被父进程或领养它的进程回收为止。

- 因为子进程调用exit后，PCB还会保留一小部分信息，这时父进程还未调用wait、waitpid来取走这些退出信息，则其成为僵尸进程
- 子进程终止之后到父进程回收它之前，这段时间就是僵尸进程
- SIGCHLD 就是当子进程退出或状态发生变化时，内核发送给父进程的通知信号，提醒父进程去用 wait 类函数回收子进程。
- wait 本身就包含回收操作。它不是单纯地等待，而是“等待某个子进程结束，并取得其退出状态，同时把该子进程从内核中回收掉”。

### 课堂题

- ```c
for(三次循环)
{
    fork()
    wait()
}

• 类似这样的逻辑，若子进程没有return 0，则父进程在子进程创建完（1→2→4）后才会被唤醒，即4次子进程后唤醒
• 若子进程有return 0，则父进程在第一次子进程创建后就被唤醒

进程间通信

• 进程协作的原因
  • 信息共享
  • 计算加速
  • 模块化
  • 方便用户
• IPC的两种模型
  • 共享内存
  • 消息传递
  • 二者无本质区别

共享内存系统

• 通信双方需要同时映射共享内存到自己的进程内
• 通信由用户进程控制而不是由OS控制

生产者消费者问题

• 生产者进程产生消费者进程所消费的信息
• 两种变体
  • 无边界缓冲区对缓冲区大小没有实际限制
  • 有界缓冲区假定存在固定缓冲区大小
  • 前者生产者从不等待，后者在缓冲区满时需要等待

共享内存

• 共享buffer采用一个循环数组和两个逻辑指针in和out来实现，in指向缓冲区的下一个空位，变量out指向缓冲区的第一个满位，二者相等时，缓冲区为空，(in+1)%BUFFER_SIZE==out时，缓冲区满
• Linux IPC 的资源限制：共享内存属于 IPC（进程间通信）的一种，系统不会让用户无限制地创建，所以内核会对消息队列、共享内存、信号量这些 IPC 资源设置上限。
• POSIX 共享内存是一种高效的 IPC 机制；它通过“命名的共享内存对象”来管理，进程首先用 shm_open() 按名字创建或打开这个对象，成功后得到文件描述符，后续再配合 mmap() 才能真正访问共享内存。（POSIX Shared Memory）
• mmap()可视作将磁盘中大文件映射到内存中

消息传递

• 消息大小是固定或可变的（需有一个结构体来描述这一消息）
• 必要条件
  • 建立通信连接
  • 通过发送/接收交换信息

通信链路实现

• 物理
  • 共享内存
  • 硬件总线
  • 网线
• 逻辑
  • 直接或间接
  • 同步or异步
  • 自动缓冲或显式缓冲

直接通信

• 进程之间明确命名，双方需要知道彼此是谁
• 链接是自动建立的
• 链路仅与一对通信进程相关联
• 每对之间只存在一个链接
• 链路通常是双向的（对称性）
• 非对称性：只要发送者指定接收者，接收者不需要指定发送者

间接通信

• 将直接通信的双方解耦，互相可以不认识，借助中间媒介
• 通过邮箱或端口来发送接收消息，每个邮箱有唯一id，进程只有在共享邮箱时才能通信（此处邮箱可理解为一种带名字的消息存放处，或是一个带标识的消息队列）
• 邮箱的所有者
  • 进程
  • 操作系统
  • 可以被转移
• 链接可能与许多进程相关联，每对进程可共享多个通信链路
• 操作
  • 创建新邮箱（端口）
  • 通过邮箱发送、接收邮件
  • 删除邮箱

同步

消息传递可以是阻塞（同步）或非阻塞（异步），非阻塞性能更高

• 阻塞发送——在接收进程或邮箱收到消息之前，发送进程阻塞
• 阻塞接收——在消息可用之前，接收进程将被阻塞
• 非阻塞发送——发送进程发送消息并继续执行
• 非阻塞接收——接收进程接收有效消息或空消息

缓存

• 零容量：链路上无消息排队，发送方必须等待接收方
• 有限容量：有限长度的n条信息，如果链路已满，则发送者才必须等待
• 无限容量：无限长的消息队列，发送方从不等待

IPC系统示例

Windows

基于端口的ALPC（本地过程调用）

基本流程为先连接，再建立专用通信端口，小消息走端口，大消息走共享内存。

• 本质上就是一种 消息传递式 IPC，只是被封装成了“本地过程调用”的形式，看起来像在调用本地函数。

1. Server 创建连接端口

2. Client 向连接端口发起连接请求

3. 系统建立一对通信端口

4. 双方分别获得对应句柄

5. Client/Server 通过通信端口交换请求和响应

6. 若数据较大，则借助共享节对象传输

管道

一种抽象的概念，其本质实现可以是消息传递或共享内存

• 单向or双向？
  • 普通管道（单向）Windows中普通管道被称为匿名管道
  • 命名管道（双向）命名管道也称为FIFO
• 全双工or半双工？
  • 半双工：双方都能发，不能同时发，普通管道
  • 全双工：双方都能同时发送接收，命名管道
• 通信进程之间关系？
  • 通常为父子进程（普通管道）
  • 不要求父子关系（命名管道）
• 网络使用or本地使用？
  • 普通管道：一般只用于本地
  • 命名管道取决于系统，Unix中还是本地IPC，Windows中可用于网络通信

例子ls | less这里的|代表匿名管道（普通管道），ls为父进程，less为子进程

客户机-服务器系统中的通信

• 套接字（Socket）：可理解为两端各自拿在手里的“通信端口”，应用程序和网络协议栈之间的接口
• socket ≈ IP地址 + 端口号 + 协议
• 远程过程调用（RPC）不要求掌握
• Socket被定义为通信的端点

RPC