操作系统-进程管理

进程

进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动 ，是系统进行资源分配和调度的一个独立单位。

要点

• 进程是程序的一次执行
• 进程是一个程序机器数据在处理机上顺序执行时所发生的活动
• 进程是程序在一个数据集合上运行的过程
• 进程是系统进行资源分配和调度的一个独立的单位（或者说基本单位）

结构

控制块（PCB）

​ 进程唯一标识（最重要的）

数据段

​ 存放原始数据（程序加载的）、中间数据（运行产生的）

程序段

​ 存放在文本区域，可被多个进程共享

特征

• 动态性：由创建而生，由撤销而亡
• 并发性：多个进程同时执行
• 独立性：独立资源的分配
• 异步性：互相独立、互不干扰

线程

线程

线程（Thread）是进程的轻型实体，也叫“轻量级进程”，是一些类活动按设定好的顺序依次执行的过程，是一系列指令的集合。

是一条执行路径，不能单独存在，必须包含在进程中。

线程是操作系统运算调度的最小单位。

为什么引入线程

提高操作系统的并发性，并减少资源的分配

属性

• 轻型实体（占用资源更少）
• 独立调度和分派的基本单位
• 可并发执行
• 共享进程资源

进程与线程

操作系统调度的最基本单位是线程

一个进程中包含多个线程，操作系统可以在多个线程间切换，这不会造成进程的调度。

线程使用的资源都是进程的，线程只有使用权。

线程进一步提高了并发性。

同一个进程中的线程，共享进程的内存空间和其他资源

重点：线程相对于进程，大大降低了创建、撤销和切换可执行实体的成本和难度。

线程的实现方式

线程如果在用户空间实现的，就是用户级线程（ULT），线程如果在内核空间实现，就是内核级线程（KLT）。

用户级线程

所有操作，包括线程创建，撤销，调度都在用户空间完成。

操作系统提供了线程库来进行这些线程的操作。

内核级线程

线程控制块在内核空间，切换是在线程之间，比用户级更快。

进程的运行

进程的状态

三种基本状态

• 就绪（Ready）

  简单来说就是可运行但是未运行的状态。

• 执行

  就绪的进程获取CPU执行权，就进入了执行状态。

  就绪到执行的步骤叫做进程调度。

  执行的进程，执行结束又回到就绪状态。

• 阻塞

  执行状态的进程，由于I/O请求，进程进入阻塞状态。

  I/O完成后，进程又从阻塞到就绪状态。

进程的五种状态

• 创建

  创建时读取进程的数据，创建 PCB 或者填写其他东西等

• 就绪

• 执行

• 阻塞

• 终止

  正常情况：当前进程执行结束后，会执行终止指令，产生一个中断，通知操作系统进程结束，终止进程。

  异常情况：出现严重的错误，进程强制终止。

进程控制

进程控制是操作系统对进程实现有效的管理，包括创建新进程、撤销已有进程、挂起、阻塞和唤醒进程切换等多种操作。

操作系统通过原语（Primitive）操作实现进程控制

原语：由若干条指令组成的，完成特定的功能，是一种原子操作（Action Operation）

原语的特点

• 原子操作，要么全做，要么全不做，执行过程不会被中断
• 在管态/系统态/内核态下执行，常驻内存
• 是内核三大支撑功能（中断处理/时钟管理/原语操作）之一

原语有很多，这里主要介绍进程控制中的原语

• 创建原语：create

  用户登录，作业调度，提供服务，应用请求，都会创建一个进程。

• 阻塞原语：block

  在运行状态时，在请求某种服务，启动某种操作，数据未到达或者无工作可做等，都会执行block原语进入阻塞状态。

• 唤醒原语：wakeup

  阻塞的进程可以继续执行，就会执行wakeup原语继续执行。

• 撤销原语：destroy

  正常终止（运行结束）、异常结束（程序内部出错）、外界干预（其他情况，一个进程关闭另一个进程等），会执行destroy原语。

挂起与激活

为了系统和用户观察和分析进程，我们将当前进程挂起，保存当前进程的状态。

将挂起的进程恢复期状态，称为激活。

挂起原语：suspeng（进程从内存拿到外存）

• 禁止就绪：放外存，不调度
• 禁止阻塞：等待事件

激活原语：active

• 活动就绪：等待调度
• 活动阻塞：等待唤醒

注：挂起和激活不是状态，它们是操作，静止就绪和禁止阻塞是状态

进程调度

进程调度也称为处理机调度。

是根据一定的算法和原则将处理机资源进行重新分配的过程。

前提

作业/进程数远远大于处理机数

目的

提高资源利用率，减少处理机空闲时间，增加操作系统吞吐量。

程序调度

一方面要满足特性系统用户的需求（快速响应），另一方面要考虑系统整体效率（系统平均周转时间）和调度算法本身的开销。

调度的层次

高级调度/作业调度

把磁盘（外存）上的应用程序，加载到内存中，创建成进程的过程。

• 把后备作业调入内存
• 只调入一次，调出一次

中级调度/内存调度

执行suspend原语，进程从内存到外存中挂起，执行Active原语，进程从外存到内存，挂起和激活的操作都是内存调度。

• 将进程调至外存，条件再调入内存
• 在内、外存对换区进行进程对换

低级调度/进程调度

• 从就绪队列选取进程分配给处理机
• 最基本的调度，频率非常高（相当于一个时间片完成）

调度方式

剥夺式/抢占式调度

• 立即暂停当前进程
• 分配处理机给另一个进程
• 原则：优先权（优先级高限制性）/短进程优先（花费时间段可优先执行）/时间片原则（时间到立马释放）

调度原则可以一次遵循多个

非剥夺/非抢占式调度

• 若有进程请求执行
• 等待直到当前进程完成或阻塞
• 缺点：适用于批处理系统，不适用分时/实时系统。

调度时机

• 进程运行完毕会进行调度（到终止状态）
• 进程时间片用完（到就绪状态）
• 进程要求I/O 操作（进入阻塞状态）
• 执行某种原语操作
• 高优先级进程申请运行（剥夺式调度）

调度过程

1. 保存镜像：记录进程现场信息（状态）
2. 调度算法：确认分配处理机的原则
3. 进程切换：分配处理机给其它进程
4. 处理机回收：从进程回收处理机

细节

1. 检查是否允许上下文切换，有可能某进程处于原语操作中，不允许切换
2. 保存当前进程的上下文，包括程序计数器和寄存器
3. 更新 PCB 信息
4. 把此进程的 PCB 移入队列，比如就绪队列，或因某种时间的阻塞队列
5. 选择另一个（就绪状态）进程执行，并更新其 PCB
6. 更新内存管理的数据结构
7. 恢复所选进程的上下文，将 CPU 执行全交给所选进程

调度算法指标

• CPU 利用率：忙碌时间/总时间
• 系统吞吐量：完成作业数/总时间
• 周转时间：作业完成时间-提交时间
  • 带权周转时间：周转时间/实际运行时间
• 等待时间：作业等待处理机调度时间
  • 关注平均值
• 响应时间：提交请求到首次响应间隔

进程调度算法

作业调度：作业从外存到内存以及从内存到外存都称为作业调度，属于高级和中级调度

进程调度：属于低级调度

先来先服务

算法内容

调度作业/就绪队列中最先入队者，等待操作完成或阻塞

算法原则

按作业/进程到达顺序服务

调度方式

非抢占式调度

适用场景

作业/进程调度

优点

有利于 CPU 繁忙型作业，充分利用 CPU 资源（没必要调来调去的，浪费很多等待时间）

缺点

不利于 I/O 繁忙型作业（需要大量的读写操作），一直等待I/O操作，非常 耗时，其它进程饥饿

短作业优先

算法内容

所需要服务时间最短的作业/进程优先服务（执行）

算法原则

追求最少的平均（带权）周转时间（完成一个作业需要的时间）

调度方式

SJF/SPF 非抢占式

适用场景

作业/进程调度

优点

平均等待/周转时间最少

缺点

长作业周转时间会增加或饥饿

估计时间不准确，不能保证紧迫任务及时处理

高响应比优先调度

算法内容

结合先来先服务（FCFS）和短作业优先（SJF），综合考虑等待时间和服务时间计算响应比，高得优先调度。

算法原则

综合考虑作业/进程的等待时间和服务时间

调度方式

非抢占式

适用场景

作业/进程调度

响应比计算

• 响应比 = （等待时间+服务时间）/服务时间，>=1
• 只有当前进程放弃执行权（完成/阻塞）时，重新计算所有进程响应比
• 长作业等待越久响应比越高，更容易获得处理机

优先级调度

算法内容

又叫优先权调度，按作业/进程的优先级（紧迫程度）进行调度

算法原则

优先级高（最紧迫）的作业/进程先调度

调度方式

抢占/非抢占式（并不能获得及时执行）

适用场景

作业/进程调度

优先级设置原则

• 静态/动态优先级
• 系统 >用户；交互性>非交互性；I/O>计算型
• 低优先级进程可能会产生“饥饿”

时间片轮转调度

算法内容

按进程到达就绪队列的顺序，轮流分配一个时间片去执行，时间片用完则剥夺。

算法原则

公平、轮流为每个进程服务，进程在一定时间内都能得到响应

调度方式

抢占式，由时钟中断确定时间到

适用场景

进程调度

优点

公平，响应快，适用于分时系统

缺点

时间片决定因素：系统响应时间（响应时间越长，效率越低，时间片越小）、就绪队列进程数量（数量越多，时间片越短）、系统处理能力（能力越强，时间片越长）。

时间片太大，相当于先来先服务；太小，处理机切换频繁，开销增大

多级反馈队列调度

算法内容

设置多个按优先级排序的就绪队列，优先级从高到低，时间片从小到大

新进程采用队列降级法，进入第一级队列，按 FCFS 分时间片，没有执行完，移到第二级，第三级。。

前面队列不为空，不执行后续队列进程

算法原则

集前几种算法的优点，相当于 优先级调度算法加上时间片轮转调度。

调度方式

抢占式

适用场景

进程调度

优点

对各类型相对公平；快速响应

终端型作业（交互型）用户：短作业优先，一般交互操作在第一个队列就运行完了

批处理作业用户：周转时间短

长批处理作业用户：长作业在前几个队列部分执行，不会导致饥饿

进程之间的协作

进程通信

概念

进程通信即进程间的信息交换。

• 进程是资源分配的基本单位，各进程内存空间彼此互相独立
• 一个进程不能随意访问它进程的地址空间

特点

• 共享存储
• 消息传递
• 管道通信

共享存储

• 基于共享数据结构的通信方式
  • 多个进程共用某个数据结构（操作系统提供并控制）
  • 由用户（程序员）负责同步处理
  • 低级通信：可以传递少量数据，效率低
• 基于共享存储区的通信方式
  • 多个进程共用内存中的一块存储区域
  • 由进程控制数据的形式和方式
  • 高级通信：可以传递大量数据，效率高

消息传递

有直接通信和间接通信两种，基于send 和 receive 这两个原语进行操作，这也是与共享存储（操作数据结构或者共享空间）的区别。

• 直接通信：点到点发送

  • 发送和接收时指明双反进程的ID

  • 每个进程维护一个消息缓冲队列
    

• 间接通信：广播信箱

  • 以信箱为媒介，作为中间实体
  • 发进程将消息发送到信箱，收进程从信箱读取
  • 可以广播，容易建立双向通信链
    

管道通信

管道用于连接/写进程的共享文件，pipe 文件（文件大小固定），本质是内存中固定大小的缓冲区。只能两个进程间建立，效率比较高，也比共享存储安全。

以流的形似读写，如果管道未满，不读数据；如果管道已经满了，就不能写了；如果管道里的数据并没有被读进程全读出去，就不能写进管道；如果管道是空的，就不读了；如果管道读完了，就删除管道的内容。

管道是半双工通信

• 同一时间只能单向通信，双工通信需要两个管道
• 以先进先出（FIFO）方式组织数据传输
• 通过系统调用read()/write()函数进行读写操作

进程同步

概念

协调进程间的相互制约关系，使它们按照预期的方式执行的过程

前提

• 进程是并发执行的，进程间存在着相互制约关系
• 并发的进程对系统共享资源进行竞争
• 进程通信，过程中相互发送的信号称为消息或事件

两种相互制约形式

• 简介相互制关系（互斥）：进程排他性地访问共享资源
• 直接相互制约关系（同步）：进程间的合作（两个进程完成一件事），比如管道通信

互斥的访问临界资源

访问过程

1. 进入区：尝试进入临界区，成功则加锁（lock）
2. 临界区：访问共享资源
3. 退出区：解锁（unlock），唤醒其它阻塞进程
4. 剩余区：其它代码

访问原则

1. 空闲让进：临界区空闲，允许一个进程进入
2. 忙则等待：临界区已有进程，其它进程等待（阻塞状态）
3. 有限等待：处于等待的进程，等待时间有限
4. 让权等待：等待时应让出CPU执行权，防止“忙等待”

软件实现方法

• 单标志法：违背“空闲让进”

  两个进程必须交互的进入临界区，如果一个不进临界区了，会影响另一个进程进入临界区。

• 双标志先检查：违背“忙则等待”

  先检查是先检查后赋值。

  但在第一次进入的时候，可能在p0进程flag[0]改为true之前，p1进程的判断已经执行，两个进程都会进入临界区
  

• 双标志后检查：违背”空闲让进“、“有限等待”

  后检查是先赋值后检查

  在一开始，p0和p1进程都赋值为true，死循环阻塞。
  

• 皮特森算法：违背“让权等待”，会发生“忙等”

  p0和p1如果进入了while，会一直自旋。

硬件实现方法

中断屏蔽：关中断/开中断

优点

• 禁止一切中断，CPU 执行完临界区之前不会切换

缺点

• 关中断可能会被滥用
• 关中断时间长影响效率
• 不适用于多处理机，无法防止其它处理机调度其它进程访问临界区
• 只适用于内核进程（该指令运行在内核态）

Test-And-Set

付出标志并设置为 true，返回旧值，是原子操作

缺点

• 也被称作 TSL 指令（Test-And-Set-Lock）
• 违背“让权等待”，会发生忙等

Swap指令（EXCHANGE，XCHG指令）

交换两个变量的值，是原子操作

缺点

• 违背让权等待

信号量

PV操作：

• P操作：wait 原语，进程等待
• V操作：signal原语，唤醒等待进程

整型信号量：违背“让权等待”，会发生忙等。

记录型信号量：进程进入阻塞状态，不会忙等。

管程

管程也可以称为监视器。

字面理解为“管理进程”，即用于实现进程同步的工具。是由代表共享资源的数据结构和一组过程（进行PV操作的函数）组成的管理程序（封装）。

组成

• 管程名称
• 局部于管程内部的共享数据结构
• 对该数据结构操作的一组过程（函数）
• 管程内共享数据的初始化语句

基本特征

• 是一个模块化的基本程序单位，可以单独编译
• 是一种抽象数据类型 ，包含数据和操作
• 信息屏蔽，共享数据只能被管程内的过程访问

条件变量

• 进入管程的进程可能由于条件不满足而阻塞
• 此时进程应释放管程以便其它进程调用管程
• 进程被阻塞的条件有多个，移入不同的条件队列
• 进程被移入条件队列后，应释放管程

死锁问题

概念

定义

多个进程由于竞争资源而造成的阻塞现象，若无外力作用，这些进程将无法继续推进。

原因

多个进程竞争系统资源，并且推进顺序非法，进程执行顺序有问题。

必要条件

• 互斥条件：共享资源的排他性访问，即共享资源资源在一个时间段内只能被一个进程访问。
• 不剥夺条件：访问时该共享资源不会被剥夺执行权。
• 请求并保持条件：保持当前资源时请求另一个资源。
• 循环等待条件：存在共享资源的循环等待链。

死锁处理策略

死锁避免：安全性算法

让系统处于安全状态，安全状态一定不会出现死锁，不安全状态可能会产生死锁，也不是一定的。

安全性算法最典型的就是银行家算法

• 系统预判进程请求是否导致不安全状态
• 是则拒绝请求，否则答应请求。

死锁检测

• 需要一种数据结构，保存有关资源的请求和分配信息
• 提供一种算法，利用这些信息检测是否形成了死锁

死锁解除

• 资源剥夺

  挂起死锁进程，剥夺其资源，将资源分配给其它进程，也就是挂起

• 撤销进程

  强制showdown，强制释其资源

• 进程回退

  回退到足以避免死锁的地步，但是要回退就需要记录进程历史信息，设置还原点