进程
# 进程
# 1. 什么是进程
# 1.1 概念
进程（Process），是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是系统进行『资源分配和调度』的一个独立单位。
几个要点
- 进程是『程序』的『一次执行』
- 进程是一个程序及其数据在处理机上顺序执行时所发生的『活动』
- 进程是程序在一个『数据集合』上运行的过程
- 进程是系统进行『资源分配和调度』的一个『独立』单位（或者说基本单位）
# 1.2 特征
# 1.2.1 结构特征
控制块（PCB）
OS根据PCB来对进程进行控制和管理，进程的创建和撤销都是根据PCB来进行的
存储：程序计数器、进程状态、CPU暂存器、存储器管理、输入输出状态等信息
PCB在新建进程时创建，并常驻内存，是进程实体的一部分，也是该进程的唯一标识
数据段
在数据区域（data region），存储（全局和静态）变量和进程执行期间使用的动态分配的内存
在堆栈（stack region）区域，存储活动过程调用的指令和本地变量
程序段
存放在文本区域（text region），存储处理器执行的代码，二进制格式
程序段可以被多个进程共享
# 1.2.2 动态性
是进程实体的一次执行过程，表现为:
- 由创建而产生
- 由调度而执行
- 由撤销而消亡
# 1.2.3 并发性
多个进程同时存在于内存中，可以同时运行
进程实体能和其它进程实体并发执行
程序的并发执行，是由PCB控制的
# 1.2.4 独立性
进程实体是能独立分配资源
进程实体能独立接受调度
进程实体能独立运行
程序的独立执行，也是由PCB控制的
# 1.2.5 异步性
进程实体间按异步方式运行
进程与进程之间相互独立、互不干扰、以不可预知的速度运行
# 1.3 进程与线程
# 1.3.1 线程概念
线程（Thread），也叫“轻量级进程”，是一系列活动按事先设定好的顺序依次执行的过程，是一系列指令的集合
线程是进程中一条执行路径，它不能单独存在，必须包含在进程中，一个进程可以有多个线程
线程是OS进行运算调度的最小单位
# 1.3.2 线程属性
- 轻型实体
- 不拥有系统资源，而是与所属进程的其它线程一起共享该进程所拥有的系统资源
- 每个线程通过自己的控制块记录线程执行的寄存器和栈等现场状态
- 独立调度和分派的基本单位
- 可并发执行
- 共享进程资源
# 1.3.3 线程与进程的比较
调度
在多线程OS中，线程是独立调度的基本单位，进程是资源分配的基本单位
同一进程中切换线程，不会引起进程切换
拥有资源
进程拥有资源，而线程（一般）不拥有资源，这样做是为了减少切换线程的开销
同一个进程中的多个线程共享该进程的资源
并发性
在多线程OS中，进程可以并发执行，线程也可以并发执行，线程的并发大大提高了OS的并发性
系统开销
创建和撤销进程，需要分配和回收相关资源，开销较大；切换进程的成本较高
相对而言，创建和切换线程的成本较低，只需要保存少量寄存器内容，开销小
地址空间和其它资源
进程间的地址空间相互独立
同一进程的线程间共享进程资源，进程间的线程彼此不可见
通信方面
进程通信需要同步或互斥手段的辅助
线程间可以直接读写数据段（如全局变量）来通信
同一进程内的线程共享该进程资源，同步和通信都更容易实现
总结
进程
(1) 作为系统『资源分配』的基本单位
(2) 可包括多个线程，至少有一个线程
(3) 进程不是一个可执行的实体，真正执行的是线程
线程
(1) 是独立运行和独立调度的基本单位
引入进程的目的在于，使多道程序并发执行，提高系统的资源利用率和吞吐量
而引入线程，是为了减少程序在并发时的时空开销，提高系统的并发性
# 1.3.4 线程的实现方式
- 用户级线程（ULT）
- 内核级线程（KLT）
有些OS同时支持用户级线程和内核级线程，实现了二者的组合连接方式
多对一模型
多个用户级线程 -> 一个内核级线程
线程管理在用户空间进行，高效
若一个用户线程使用内核服务时阻塞，则整个进程阻塞
一对一模型
每个用户级线程 -> 一个内核级线程
并发能力较强，一个线程阻塞不影响其它线程
内核线程创建较多，影响性能
多对多模型
n个用户级线程 -> m个内核级线程，m <= n
克服了多对一模型并发度不高的缺点
克服了一对一模型内核级线程开销太大的缺点
# 2. 进程是怎么运行的
# 2.1 进程的状态
进程的生命周期：从创建到终止的过程
- 就绪（Ready）
进程已分配到除CPU以外的所有必要资源后， 只要再获得CPU，便可立即执行，进程这时的状态称为就绪状态
可运行未运行状态
多个处于就绪状态的进程会形成一个就绪队列
- 执行（Running）
进程已获得CPU（执行权）， 其程序正在执行
在单处理机系统中，只有一个进程处于执行状态； 在多处理机系统中，则有多个进程处于执行状态
- 阻塞（Blocked）
正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，即阻塞
也称为等待状态或封锁状态
发生阻塞的典型事件
- 请求I/O
- 申请缓冲空间
- 进程同步
阻塞状态的进程也会排成一个队列，由于不同原因导致的阻塞，可以会形成多个队列
# 2.2 进程状态转换
挂起称为静止状态，非挂起称为活动状态
(1) 活动就绪→静止就绪
未被挂起的就绪状态（Readya）--(Suspend原语)-->静止就绪状态（Readys），Readys状态不会被调度
(2) 活动阻塞→静止阻塞
未被挂起的阻塞状态（Blockeda）--(Suspend原语)-->静止阻塞状态（Blockeds），Blockeds状态不会被调度
(3) 静止就绪→活动就绪
静止就绪状态（Readys）--(Active原语)-->活动就绪状态（Readya），Readya状态可以被调度
(4) 静止阻塞→活动阻塞
静止阻塞状态（Blockeds）--(Active原语)-->活动阻塞状态（Blockeda），Blockeda状态可以被调度
# 2.2 进程控制
# 2.2.1 原语（Primitive）
控制进程的程序段，进程控制一般是由OS的内核中的原语来实现的
原语是不可再分的原子操作(Action Operation)，执行过程中不会被打断
原子操作在管态下执行， 常驻内存
# 2.2.2 进程创建
步骤
- 为一个新进程创建PCB，并填写必要的管理信息
- 把该进程转入就绪状态并插入就绪队列之中
场景
- 系统已为其分配了PCB
- 填写了进程标识
- 进程尚未进入主存（未分配）
- 进程不能被调度执行
目的
- 保证进程的调度必须在创建工作完成后进行
- 确保对进程控制块（PCB）操作的完整性
- 增加了管理的灵活性
- OS可以根据系统性能或主存容量的限制推创建状态进程的提交
- 下一个状态是就绪状态
触发创建的场景
- 用户登录
- 作业调度
- 提供服务
- 应用请求
# 2.2.3进程终止
步骤
- OS将该进程标记为终止
- 资源释放和回收
进入终止的原因
- 正常结束
- 自然结束：运行到Holt指令（最后一条指令）时，将产生一个中断，去通知OS本进程已经完成
- 异常结束
- 由于出现某些错误和故障而迫使进程终止
- 越界错误
- 保护错误
- 非法指令
- ...
- 外界干预
- 进程应外界的请求而终止运行
- 被操作员或操作系统终结
- 被其他有终止权的进程（父进程）所终结
# 2.2.4 阻塞和唤醒
- 引起进程阻塞和唤醒的事件
- 请求系统服务 - 等待OS分配打印机服务
- 启动某种操作 - 等待I/O操作完成
- 新数据尚未到达 - B进程等待A进程的数据输入
- 无新工作可做 - 进程空闲，等待新任务到来
- 进程阻塞过程
- 调用阻塞原语block()把自己阻塞
- 立即停止执行
- 由执行状态（Running）改为阻塞状态（Blocked）
- 将PCB插入阻塞队列
- 因不同事件进行阻塞的进程可能会形成多个阻塞队列，直到调度程序进行重新调度它们
- 进程唤醒过程
- 有关进程调用唤醒原语wakeup( )， 将等待该事件的进程唤醒
- 把被阻塞的进程从等待该事件的阻塞队列中移出
- 将其PCB中的现行状态改为就绪，再将该PCB插入到就绪队列中
- 被唤醒的进程进入就绪状态（Ready），而非执行状态（Running）
- 被阻塞进程必须由其它进程唤醒，否则，将一直处于阻塞状态，从而再无机会继续运行
# 2.2.5 进程挂起
使正在执行的进程暂停执行，若此时用户进程正处于就绪状态而未执行， 则该进程暂不接受调度， 以便用户研究其执行情况或对程序进行修改，此时，我们把这种静止状态称为挂起状态
挂起的原因
- 终端用户的请求 - 发现可疑问题，希望进程静止下来
- 父进程请求 - 父进程希望挂起子进程，以便协调各子进程间的活动
- 负荷调节的需要 - 负荷较重，挂起不重要的进程
- 操作系统的需要 - OS检查资源使用情况，或进行记账
挂起过程
- 首先检查被挂起进程的状态， 若处于活动就绪状态， 便将其改为静止就绪
- 对于活动阻塞状态的进程，则将之改为静止阻塞
- 若被挂起的进程正在执行，则转向调度程序重新调度
- 把该进程的PCB复制到某指定的内存区域，方便用户或父进程考查该进程的运行情况
进程激活
- 激活原因 - 父进程或用户进程请求激活
- 激活过程
- 激活原语先将进程从外存调入内存
- 检查该进程的现行状态，若是静止就绪，便将之改为活动就绪
- 若为静止阻塞，便将之改为活动阻塞
- 激活后需要根据处理机调度策略和进程优先级等条件决定该进程是否执行
# 2.2.6进程切换
处理机从一个正在运行的进程上切换到另一个进程去执行
切换过程
- 0S检查是否允许上下文切换，有可能某进程处于原语操作中，不允许切换
- 保存当前进程的上下文，包括程序计数器和寄存器
- 更新PCB信息
- 把此进程的PCB移入队列，比如就绪队列，或因某种事件的阻塞队列
- 选择另一个（就绪状态）进程执行，并更新其PCB
- 更新内存管理的数据结构
- 恢复所选进程的上下文，将CPU执行权交给所选进程
# 2.2.7 状态转换图
(1) NULL→创建： 一个新进程产生时，该进程处于创建状态
(2) 创建→活动就绪：在当前系统的性能和内存的容量均允许的情况下， 完成对进程创建的必要操作后，相应的系统进程将进程的状态转换为活动就绪状态
(3) 创建→静止就绪：考虑到系统当前资源状况和性能要求， 并不分配给新建进程所需资源， 主要是主存资源，相应的系统进程将进程状态转为静止就绪状态，对换到外存， 不再参与调度， 此时进程创建工作尚未完成
(4) 执行→终止： 当一个进程到 了自然结束点 一个进程到达了自然结束点， 或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结， 进程即进终止状态
# 2.3 进程调度
# 2.3.1 概念
在多道程序系统中，根据一定的算法（公平、高效）将处理机重新分配给就绪队列中的进程去执行，以实现进程并发执行的过程
调度的前提是，进程的数量往往远大于处理机个数，造成进程争用处理机的现象，所以需要将处理机资源在不同的进程间调度
进程调度的主要问题就是采用某种算法合理有效地把处理机分配给进程，其调度算法应尽可能提高资源的利用率，减少处理机的空闲时间
调度的层次
1）高级调度
- (High-Level Scheduling)，又叫作业调度
- 按一定原则从外存处于后备状态的作业中挑选一个（或多个），给它们分配资源（内存、I/O设备等）并建立进程，以使它们获得竞争处理机的权利
- 把后备作业调入内存运行
- 只调入一次，调出一次
- 通俗的说，就是把程序从硬盘加载到内存中运行的过程
2）中级调度
- (Intermediate-Level Scheduling)，又叫内存调度，提高内存利用率和系统吞吐量
- 将暂时不能运行的进程挂起并调至外存（比如硬盘上的虚拟内存）等待，条件合适时再调入内存就绪
- 在内、外存对换区进行进程对换
3）低级调度
- (Low-Level Scheduling)，又叫进程调度
- 是一种最基本的调度，频率非常高（几十毫秒一次，相当于一个时间片完成）
- 从就绪队列中选取进程分配给处理机
三级调度的关系三级调度的关系
1）作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将不能运行的进程挂起。中级处于作业和进程调度之间
2）作业调度次数少，中级略多，进程调度最高
3）进程调度是最基本的
# 2.3.2 进程调度方式
- 剥夺调度方式
- 抢占式
- 立即暂停正在执行的进程，将处理机分配给另一个更重要或优先级更高的进程
- 更高效
- 原则
- 优先权
- 短进程优先
- 时间片原则
- 非剥夺调度方式
- 非抢占式（或协作式）
- 若有进程请求执行，等待当前正在执行进程完成或因某种原因阻塞，才把处理机分配给请求进程
- 优点是实现简单，系统开销小（切换频次低了）
- 缺点是适用批处理系统，不适用大多分时和实时系统
- 衡量进程调度性能指标
- 周转时间
- 响应时间
- CPU-I/O执行期
# 2.3.3调度的时机、切换与过程
时机
①正在运行的进程运行完毕；
②运行中的进程要求I/O；
③执行某种原语操作；
④一个比正在运行进程优先数更高的进程申请运行（在可剥夺调度方式下）；
⑤分配给运行进程的时间片已经用完等
过程
（1）记录系统中所有进程的现场信息。
（2）确定分配处理机的原则。
（3）分配处理机给进程。
（4）从进程收回处理机
# 2.3.4 调度的基本准则
CPU利用率 - 越高，说明该资源使用率越高
系统吞吐量
- 单位时间内CPU完成作业量
- 长作业耗时，短作业则能提高吞吐量
- 调度算法和方式不同，对OS吞吐量产生较大影响
周转时间
- 作业从提交到完成经历的时间
- 包括等待、就绪队列的排队，处理机上的运行、输入输出花费时间的总和
等待时间
- 进程等待时间总和
- 调度算法不影响作业执行或输入输出时间，只影响作业在就绪队列中等待时间
- 所以，衡量调度算法的优劣，考察等待时间即可
响应时间
- 用户提交请求到系统首次响应花费的时间
- 交互是系统中衡量调度算法的重要准则
- 应尽量降低响应时间，控制在用户可接受范围内
调度程序一方面要满足特定系统用户的要求（实时和交互进程要求快速响应），另一方面要考虑系统整体效率（减少整个系统进程平均周转时间）和调度算法本身的开销
# 2.3.5 典型的调度算法
先来先服务（FCFS）调度算法
适用于作业调度和进程调度
取作业队列中或就绪队列中最先入队的进程进行调度，并等待操作完成，或作业执行完成或因某种原因阻塞时释放处理机
FCFS属于不可剥夺算法，简单但效率低，可能导致后续作业长时间得不到执行，不能作为分时和实时系统的主要调度策略
是使用优先级作为调度策略的系统中，相同优先级作业一般按照FCFS原则处理
有利于CPU繁忙型作业，不利于I/O繁忙型作业
短作业优先（SJF）调度算法
短作业调度（SJF）：从后备队列中选择一个或多个估计运行时间最短的作业运行；
短进程调度（SPF）：从就绪队列中选择一个或多个估计运行时间最短的进程运行，直到完成或阻塞
优先级调度算法
又叫优先权调度算法
可用于作业调度和进程调度
优先级用于描述作业的紧迫程度
优先级能否改变
- 静态优先级
- 动态优先级
非剥夺式调度时，新的更高优先级进程并不能获得及时执行
剥夺式调度时，新的更高优先级进程一旦进入就绪队列，则当前进程立即暂停，并将处理机分配给新进程
高响应比优先调度算法
主要用于作业调度，是对FCFS和SJF的综合平衡
调度时先计算作业的响应比
- 作业等待时间相同，服务时间越短，响应比越高
- 服务时间相同，响应比由等待时间决定，等待越久，响应比越高
- 长作业的响应比可以随等待时间提高，等待愈久，响应比越高，更容易获得处理机
时间片轮转调度算法
适用于分时系统
将所有就绪进程按照到达顺序入队，并总是选择第一个进程执行（先来先服务），但仅能运行一个时间片（如100ms），时间到，立刻剥夺该进程执行权并重新入队（队尾），处理机取下一个进程运行
时间片大小对OS性能影响很大
多级反馈队列调度算法（集合前几种的优点）
集合了前几种算法的优点：相当于时间片轮转调度算法 + 优先级调度算法
动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面系统目标
实现思想
- 1）设置多个就绪队列，为不同队列设置不同的优先级（逐次降低）
- 2）不同队列中进程时间片不同，优先级高的队列中进程时间片小，反之则长（倍长法）
- 3）新进程采用队列降级法：进入第1级队列（队尾，遵循FCFS），没有执行完，移到第2级，未完，移到第3级。。。
- 4）前面队列不为空，不会执行后续队列的进程
优势
- 1）终端型作业用户：短作业优先
- 2）短批处理作业用户：周转时间较短
- 3）长批处理作业用户：经过前面几个队列已经得到部分执行，不会长期得不到处理（饥饿）
# 3. 进程之间怎么协作
# 3.1 进程通信
进程通信即进程间的信息交换
共享存储（Shared-memory）
基于共享数据结构的通信方式
基于共享存储区的通信方式
数据的发送方不关心数据由谁接收，数据的接收方也不关心数据是由谁发送的，存在安全隐患
消息传递（message-passing）
利用OS提供的消息传递方式进行通信
通过发消息和收消息两个原语进行操作
以格式化的消息(message)进行传递
两种方式
- 直接通信
- 点到点发送
- 发送和接收时指明双方进程的ID
- 发送进程直接发消息到接收进程的消息缓冲队列上，接收进程从自己的消息缓冲队列上读取消息
- 间接通信
- 以信箱为媒介进行传递，可以广播
- 发送进程直接发消息到中间实体（信箱）上，接收进程从中间实体上读取消息
- 很容易建立双向通讯链
管道通信（Pipe）
基于文件系统和缓冲思想实现的一种通信方式
管道以先进先出(FIFO)方式组织数据传输
管道是一个单向通信信道，如果进程间要进行双向通信，通常需要定义两个管道
管道通过系统调用read(), write()函数进行读写操作
# 3.2 进程同步
# 3.2.1 基本概念
前提：在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系，比如互相发送消息、进行合作、互相等待。
概念：协调进程之间的相互制约关系，使得各进程按一定的速度执行的过程称为进程间的『同步』
具有同步关系的一组并发进程称为『合作进程』，合作进程间互相发送的信号称为『消息或事件』
进程同步是协调进程之间的相互制约关系的过程，也可以说，进程同步就是维护并发进程间的『协作』关系
并发执行中可能存在的两种形式的制约关系
- 直接相互制约关系
- 源于进程间的合作
- 例如管道通信方式，写入共享文件（Pipe）的进程进行write操作时，读进程阻塞；反之，读进程进行read操作时，写进程阻塞
- 间接相互制约关系
- 同一系统中的进程，通常都共享着某种系统资源
# 3.2.2 临界资源
常见临界资源
- 输入机、打印机、磁带机
- 消息缓冲队列、变量、数组、缓冲区
访问方式
- 进程间应采取『互斥』方式，实现对临界资源的访问
临界区
- 进程中用于实现进程互斥的那段代码称为临界区
- 若能保证诸进程互斥地进入临界区，便可实现诸进程对临界资源的互斥访问
访问过程
1）进入区
- 进入临界区前检查权限，否则等待/阻塞
- 设置正在访问临界区的标识
2）临界区
- 访问临界资源的代码
3）退出区
- 将正在访问临界区的标识清除
4）剩余区
- 代码剩余部分
# 3.2.3 同步
同步的基本义：随时间的变化保持一定的相对关系
直接制约关系，比如管道通信方式
# 3.2.4 互斥
互斥的基本义：相互独立、互不干扰的工作
间接制约关系，比如共享资源方式
几个进程若共享同一临界资源，它们必须以『互斥』的方式使用这个临界资源
系统中同时存在有许多进程，它们共享各种资源，然而有些资源每次只能让一个进程所使用
互斥机制下临界区访问原则
- 空闲让进 - 临界区空闲，可以允许一个进程进入临界区
- 忙则等待 - 已有进程进入临界区，其它试图进入的进程应等待
- 有限等待 - 确保等待的进程，进入临界区前的等待时间有限
- 让权等待 - 不能进入临界区时，应让出CPU执行权，防止忙等待（即占用CPU执行权的等待）
# 3.2.5 实现临界区互斥的基本方法
软件实现方法
在进入区设置并检查一些标识，来判断是否有进程在临界区中，若有则在进入区循环检查并等待；进程离开临界区后在退出区修改标识
算法一：单标志法
- 设置一个公用整型变量turn，用于指示被允许进入临界区的进程编号
- 确保每次只允许一个进程进入临界区
- P0离开临界区后，标记置为turn=1，而P1未进入临界区，此时其它进程无法进入，造成资源浪费
算法二：双标志法先检查
算法三：双标志法后检查
算法四：皮特森算法（Peterson's Algorithm）
硬件实现方法
中断屏蔽方法
TestAndSet（TS指令/TSL指令）
Swap指令（XCHG指令）
# 3.3 信号量
- 整型信号量
- 记录型信号量
- 利用信号量实现同步
- 利用信号量实现进程互斥
- 利用信号量实现前驱关系
- 分析进程同步和互斥问题的方法步骤
# 3.4 管程
“管理进程”，即用于实现进程同步的工具。是由代表共享资源的数据结构和一组过程（进行PV操作的函数）组成的管理程序（封装）。
管程的组成
管程名称 局部于管程内部的共享数据结构 对该数据结构操作的一组过程（函数） 管程内共享数据的初始化语句
管程的基本特性
是一个模块化的基本程序单位，可以单独编译 是一种抽象数据类型，包含数据和操作 信息掩蔽，共享数据只能被管程内的过程访问
# 4. 如何处理死锁问题
# 4.1 死锁的概念
定义
多个进程由于竞争资源而造成的阻塞现象，若无外力作用，这些进程将无法继续推进。
相似概念：饥饿，等待时间过长以至于给进程推进和响应带来明显影响，“饿而不死”
死锁产生的原因
系统资源的竞争
进程推进顺序非法
死锁产生的必要条件
互斥条件
不剥夺条件
请求并保持条件
循环等待条件
# 4.2 死锁处理策略
预防死锁
- 破坏互斥条件
- 破坏不剥夺条件
- 破坏请求和保持条件
- 破坏循环等待条件
避免死锁
- 系统安全状态
- 银行家算法
- 安全性算法举例
死锁的检测与解除
- 资源分配图
- 死锁定理
- 死锁解除