进程

进程是程序的一次执行过程，是一个程序及其数据在处理机上顺序执行时所发生的活动

进程模型

进程组成

进程由以下三个部分组成

• 程序段：存放程序代码本身
• 数据段：存放程序运行过程中处理的各种数据
• PCB：进程管理所需的数据都放在这里，PCB是进程存在的标志

其中操作系统管理进程，主要是管理进程所对应的PCB

PCB中包括了进程的描述信息（进程标识符 PID、用户标识符 UID、父进程、子进程等）；进程控制和管理信息（进程优先级、进程当前状态、进程同步和通信机制等）；资源分配清单（程序段指针、数据段指针、外设资源等）；处理器信息（如各类寄存器的值，程序计数器等等）

进程的组织

进程的组织其实就是组织进程所对应的PCB

主要可以用两种数据结构实现：

• 链接方式：即按照进程状态将PCB分为多个队列，同时操作系统对各队列的指针进行管理（比如进程的就绪队列等等）
• 索引方式：根据进程状态建立索引表，操作系统持有各表的指针

进程控制

进程控制就是对系统中的所有进程实施有效的管理，如创建新进程、撤销已有进程、实现进程状态转换等功能

进程控制使用原语实现

进程控制会导致进程状态的转换，主要需要实现如下控制：

• 更新PCB中的信息
• 将PCB插入合适的队列
• 分配/回收资源

进程的特性

• 动态性：最基本特征。进程是程序的一次执行过程，是动态地产生、变化和消亡的
• 并发性：内存中有多个进程实体，各进程可以并行执行
• 独立性：进程是能独立运行、获得资源、接受调度的基本单位
• 异步性：各进程按各自独立的、不可预测的速度向前推进，异步性会导致并发程序执行结果的不确定性，操作系统要提供“进程同步机制”来解决异步问题
• 结构性：每一个进程都会配置PCB

进程的状态与转换

进程的状态

进程有三个基本状态：运行、就绪、阻塞/等待，此外还有创建状态和终止状态

• 运行状态(Running)：占有CPU，并在CPU上运行
• 就绪状态(Ready)：进程已经具备一切运行条件，除了没有空闲CPU，导致暂时不能运行
• 阻塞状态(Waiting/Blocked)：等待某一事件或资源而暂时不能运行，比如等待操作系统分配打印机、等待磁盘读写
• 创建状态(New)：操作系统为该进程分配所需内存等系统资源，为其创建、初始化PCB(分配PID等等)
• 终止状态(Terminated)：进程运行结束，或者出现Bug导致无法继续执行，操作系统需要撤销进程 完成资源回收，撤销PCB

进程状态转换

进程间通信（IPC）

进程通信

进程通信就是进程之间的信息交换。

由于各进程的内存地址空间相互独立，一个进程不能直接访问另一个进程的地址空间，所以就产生了进程间通信（IPC）问题

1、共享存储

使得多个进程可以访问同一块内存空间，不同进程可以看到对方进程对共享内存中数据的更新。

两个进程对共享空间的访问必须是互斥的，所以该方法需要依靠某种同步操作，如互斥锁和信号量等

2、管道通信

管道是指用于连接读写进程的一个共享文件

管道只能采用半双工通信，某一时间段只能实现单向传输，同时各进程也必须互斥的访问管道

3、消息传递

进程间的数据交换以格式化的消息（Message）为单位，进程通过操作系统提供的“发送消息/接收消息”原语进行数据交换，如消息队列等等

进程同步

进程同步又叫进程的“直接制约关系”，为了完成某种任务而建立两个或多个进程，这些进程因为需要在某些位置上协调工作次序而产生制约关系。

进程具有异步性，各并发执行的进程以各自独立、不可预测的速度向前推进。

但有时需要保证不同的进程按照特地的次序推进，比如管道读、写数据两个操作必需按照“写数据->读数据”的顺序执行，因此就产生了进程同步的需求

进程互斥

进程互斥指一个进程访问某些临界资源时，另一个想要访问该临界资源的进程必需等待，直到资源被释放。又叫“间接制约关系”

临界资源：一个时间段内只允许一个进程使用的资源（比如一些物理设备，变量数据，内存缓冲区）

进程互斥主要包括三个部分

1. 进入区：负责检查是否可以进入临界区，若可以进入则设置“正在访问临界资源的标志”（上锁），阻止其它进程同时进入临界区
2. 临界区：负责访问临界资源
3. 负责解除“正在访问临界资源的标志”（解锁）

原则

• 空闲让进：临界区空闲，应允许一个进程访问
• 忙则等待：临界区正在被访问时，其它试图访问的进程需要等待
• 有限等待：在有限的时间内进入临界区，保证不会饥饿
• 让权等待：进不了临界区的进程，释放处理机，防止忙等

进程互斥软件实现方法

1、单标志法

两个进程在访问完临界区后会把临界区的权限转交给下一个进程（每个进程进入临界区的权限只能被另一个进程赋予）

因此如果一个进程一直不使用临界区资源，会导致即使临界区空闲，仍然无法访问，违背”空闲让进“原则

2、双标志先检查

使用一个数组来标记各进程是否想进入临界区，每个进程在进入临界区前查看是否有其他进程想访问临界区，若没有，则设置自身标记再访问临界区。

如下，若按照①->⑤->…进行执行的话，会使得P0和P1同时进入临界区，违背忙则等待

原因：进入临界区的“检查”与“上锁”两个处理不是一气呵成的，两者之间可能会发生进程切换

3、双标志后检查

即改为先上锁、再检查

当按照①->⑤->…进行执行的话，会使得P0和P1都无法进入临界区，违背空闲让进和有限等待

4、Peterson算法

若几个进程都想进入临界区，则主动让对方先进入临界区

是几个方法中最好的，但违背让权等待，可能造成CPU资源的浪费

信号量机制

软件解决方案的主要问题是由“进入区的各种操作无法一次性完成” ，因此如果能把进入区、退出区的操作都用“原语”实现就能避免问题。

信号量：一个标识系统中某种资源数量等标志的变量

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而实现进程的互斥与同步

即wait(S)原语和signal(S)原语，也即PV操作，可以简写为P(S)、V(S)

因此利用信号量机制实现进程的互斥与同步只需要将PV操作置于合适的位置并且在PV操作内对信号量进行合理的操作即可

进程调度

任务很多资源有限，就需要确定某种规则来决定任务的处理顺序

进程的调度就是从就绪队列中按照一定算法选择一个进程并将处理机分配给他运行，以实现进程的并发执行

调度概述

进程调度的时机

• 进程自动放弃处理机：正常终止、异常终止、主动请求阻塞
• 进程被动放弃处理机：时间片用完、更高优先级进程进入就绪队列（被抢夺）

调度算法的评价指标

• CPU利用率：CPU忙碌时间(+IO时间)/总时间
• 系统吞吐量：总共完成的作业数/总时间
• 周转时间
• 等待时间
• 响应时间

批处理系统中的调度算法

1、先来先服务（FCFS）

作业/进程谁先到后备队列的谁先得到服务，是非抢占式算法

优点：公平，算法简单

缺点：对长作业（进程）有利，对短作业不利（带权周转时间很大） ，不会导致饥饿

2、最短作业优先（SJF）

算法思想：追求最少的平均等待时间，最少平均周转时间，最少平均带权周转时间

算法规则：需要服务时间最短的作业、进程先得到服务，可以实现为非抢占式也可以实现为抢占式

优点：“最短的”平均等待时间、平均周转时间

缺点：不公平，短作业有利，长作业不利。 可能导致饥饿，如果有源源不断的短作业到来，长作业可能一直得不到服务（饿死）

3、高响应比优先

算法思想：综合考虑作业/进程的等待时间和服务时间

算法规则：每次调度时选择响应比最高的作业/进程。响应比=(等待时间+要求服务时间)/要求服务时间

非抢占式，除非当前作业/进程主动放弃处理机，才需要调度

优点：综合考虑了等待时间和运行时间

交互式系统中的调度算法

1、时间片轮转（round robin）

常用于分时操作系统，注重响应时间，而非周转时间

算法思想：公平、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

算法规则：按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片(如100ms) 。若进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队。

抢占式算法，由时钟中断通知CPU时间片已到，不会饥饿

缺点：高频率进程切换，有一定的开销，不区分任务的紧急程度

2、优先级调度

调度时选择优先级高的进程，适用于实时操作系统，可能发生饥饿

根据优先级是否可以动态改变分为静态优先级和动态优先级两种

通常系统进程优先级高于用户进程，前台进程优先级高于后台进程

3、多级反馈队列

对之前所述算法的综合，抢占式，可能导致饥饿，Unix即使用该算法

算法过程

如上图所示：

1、设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

2、新进程到达时进入第1级队列，按FCFS原则等待分配时间片，若时间片用完还未运行结束，则进入下一级队列队尾，若已经在最后一级队列，则重新放回该队列队尾

3、只有第k级队列为空，才会为k+1级队列分配时间片用于进程调度

4、该算法是抢占式的，在第k级队列的进程运行时，若上层队列进入了一个新进程，则该新进程会抢占处理机

死锁

死锁的概念

并发环境下，各进程因为竞争资源造成的：互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象

其中资源泛指一类需要排他性使用的对象，对不可剥夺资源分配不合理可能导致死锁

死锁是“循环等待对方手中的资源”导致的，因此若有死锁现象，则至少有两个或两个以上的进程同时发生死锁

死锁产生的条件

• 互斥条件：争抢互斥资源
• 不可剥夺条件：进程获得的资源未使用完成，其它进程不能强行夺走，只能等待主动释放
• 请求和保持条件：进程已经保持了至少一个资源，但是又提出新的资源请求，同时该资源被其它进程占有，此时请求进程被阻塞，但是对自己拥有资源又保持不放
• 循环等待条件：死锁时存在循环等待链（比如哲学家吃饭问题每个哲学家拿出一个筷子）

死锁的处理策略

预防死锁

即破坏上述死锁产生的四个条件

避免死锁

安全序列：系统按照这种序列分配资源，能让每个进程都顺利完成

不安全状态：只要存在一个安全序列，系统就是安全状态。找不到安全序列，即为不安全状态

不安全状态可能发生死锁（不一定发生），安全状态一定不会死锁

避免死锁即避免系统进入不安全状态（银行家算法），即构建最大需求、已分配资源、最多还需要资源的表格并进行比较，从而找到一条安全序列

检测和解除死锁

死锁发生后，操作系统负责检查死锁并解除死锁

检测死锁

死锁定理：如果某时刻资源分配图是不可完全简化的，那么此时进程死锁

因此检测死锁就是在资源分配图中，不断找出能够变为“孤点”的进程，在一系列操作中若能消去图中的所有变，则称该图是可完全简化的

同时，用死锁检测算法化简资源分配图后，还连着边的就是死锁进程

死锁解除

• 资源剥夺法：挂起死锁进程并剥夺其所有资源（必须防止饥饿）
• 终止进程法：直接终止，可能造成系统资源的浪费
• 进程回退法：让死锁进程回退到足以避免死锁的地步

参考：

《现代操作系统》

https://mubu.com/doc/Cd-Y4YOfkh