Chapter 2 Process Management

进程基本概念与状态切换

1.1 基本概念

• 进程是可并发执行的程序在某个数据集合中进行的一次计算活动，是操作系统分配系统CPU，进行资源调度的最小单位，线程是任务调度和执行的最小单位。
• 进程映像：程序段、数据段、PCB
  • Process Control Block（PCB）进程控制块：pid时进程唯一性的标记，PCB是进程存在的唯一标志。系统通过进程的PCB了解进程的状态和相关信息，从而对进程进行管理。PCB包含进程描述信息、资源分配信息、处理机控制信息。

1.2 状态切换模型

1. 三状态模型

2. 五状态模型

   

3. 七状态模型

   

[注]挂起等待态→挂起就绪态：引起进程等待的事件发生之后，相应的挂起等待态进程将转换为挂起就绪态。

进程控制

2.1 进程创建

• 为进程分配一个新的Pid，并申请一个新的PCB。若无可用PCB，则申请失败。
• 为进程分配资源，即为进程的程序段、数据和用户栈分配必要的内存空间，若无足够内存资源，则进程进入阻塞态，等待内存资源充足后唤醒。
• 初始化PCB，包含进程描述信息、资源分配信息、处理机控制信息，进程优先级等。
• 将新进程插入就绪队列，等待被调度运行。

2.2 进程终止

终止分为进程正常结束，出现异常事件终止以及外界干预终止三种。

• 根据被终止的进程的Pid检索PCB，查询当前进程状态。
• 若进程处于执行状态，则立刻停止进程的执行，CPU立刻转去执行其他任务。
• 若进程有子进程，则先将其所有子进程终止。
• 子进程将拥有的资源全部归还给父进程或操作系统。
• 将该PCB从队列中删除。

2.3 进程阻塞

• 根据被终止的进程的Pid检索PCB。
• 若进程处于执行状态，则保护现场，将其转换为阻塞态，停止运行。
• 将PCB插入等待队列，CPU转去执行其他任务。

2.4 进程唤醒

• 根据被终止的进程的Pid在等待队列中检索PCB。
• 将其从等待队列中移出，变为就绪态。
• 将PCB插入就绪队列，等待被调度执行。

2.5 进程切换

• 保存CPU上下文环境
• 更新进程PCB
• 将PCB插入就绪或等待队列
• 根据调度算法选择新的进程进入CPU，并更新新进程PCB
• 更新内存数据
• 恢复CPU环境

进程通信

• 共享存储：通信的进程之间共同直接访问一块共享空间，进行读写操作实现进程间通信（通过PV操作实现互斥同步）。
• 消息传递
  • Send发送原语：将消息发送到指定进程。
  • Receive接收原语：接收任意进程发来的消息。
• 管道通信：模拟管道信号运输，是一种半双工的通信方式，写进程以字符流形式将大量数据写入管道，读进程从管道中读数据。

线程概念与比较

线程是CPU执行任务的最小单元，是被系统独立调度和分派的最小单位。

4.1 线程和进程的比较

方面	线程	进程
调度	独立调度的最小单位	资源分配的最小单位
资源	仅拥有必须资源，但可访问所在进程的系统资源	拥有执行任务的全部资源
并发	可并发执行	可并发执行
开销	仅需保存少量寄存器内容，开销较小	创建和撤销进程，都需要系统为其分配和回收资源，开销较大
空间	一个进程的线程对其他进程不可见，一个进程内的线程相互可见	进程的地址空间相互独立
通信	线程间可直接操作进程数据段	通过进程同步互斥实现

4.2 进程和程序的比较

方面	程序	进程
状态	一组有序指令集合，静态	程序及其数据在计算机上的一次执行活动，动态
时长	一组代码的集合，永久存在	程序的依次执行过程，具有一定的生命周期，从创建到终止
创建	程序不可以创建程序	进程可以创建进程
执行	一个程序构成多个进程	一个进程可以执行多个程序
构成	代码段	程序、数据和PCB

线程实现

5.1 内核级线程

• 线程管理的所有工作都由内核管理，应用程序仅有一个到内核级线程的接口。内核保存着进程中各个线程的状态信息，为其维护着上下文环境。
• 优点：一个线程被阻塞时，其他线程仍可正常工作，并发性良好 。
• 缺点：每创建一个用户级线程都需要一个内核级线程与之对应，开销大性能降低。

5.2 用户级线程

• 线程管理的所有功能都由应用程序完成，内核感受不到多线程的存在。
• 优点：线程的切换不需要转到内核空间，也不需要创建新的内核线程，节省开销。
• 缺点：一个线程被阻塞时，进程的所有线程都被阻塞，不可并行。

线程实现方式

处理机调度

对CPU进行分配，按照一定的算法从就绪队列中选择一个进程进入CPU，进程开始运行，从而实现进程的并发操作。

6.1 调度层次

• 作业调度（高级）：指内存和辅存之间的调度，选择后备队列中的作业分配资源，并建立相应的线程。每个作业仅调入一次，调出一次。
• 内存调度（中级）：指挂起的进程在内存和外存之间的调度。当内存有空闲时，可重新调入内存，挂在就绪队列上等待。
• 进程调度（低级）：按照某种调度算法从就绪队列中选择一个进程并将CPU分配给它，是系统中最基本的调度。

处理机调度流程

6.2 调度算法

调度基本准则：CPU利用率、系统吞吐量、周转时间、等待时间、响应时间。

• FIFO 先进先出
• SJFS 短作业优先
• RR 时间片轮转
• Priority 优先级
• High-Response 高响应比 = (等待时间 + 运行时间)/运行时间
• Multi-Return 多反馈队列

进程同步

7.1 基本概念

• 指协调不同进程之间的相互制约关系。
• 临界区：访问临界资源的代码片段。
• 临界资源：一次仅允许一个进程使用的资源。
• 同步：直接制约关系，进程之间相互合作。
• 同步机制准则： 空闲让进、忙则等待、有限等待、让权等待
• 互斥：间接制约关系，一个进程进入临界区，另一进程必须等待。
• 同步机制准则： 空闲让进、忙则等待、有限等待、让权等待
• 信号量：相当于旗帜，表明关键代码段能否并发调用。
• 管程：代表共享资源的数据结构，管理共享变量以及操作过程。

7.2 经典同步问题

• 生产者——消费者
• 读者、写者
• 哲学家进餐
• 苹果橘子
• 理发师理发
• 独木桥
• 吸烟者
• 公交车
• 飞机票

死锁

8.1 死锁产生

8.2 死锁策略