# 进程简介

# 进程的概念

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

1. 进程是程序的一次执行
2. 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
3. 进程是程序在一个数据集合上运行的过程
4. 进程是系统进行资源分配和调度的一个独立单位

# 进程的结构和特征

# 进程的结构

1. 控制块（PCB）：进程的唯一标识
2. 数据段：存放原始数据的中间数据
3. 程序段：存放在文本区域，可被多个进程共享

# 进程的特征

1. 动态性：由创建而生，由撤销而亡
2. 并发性：多个进程同时运行
3. 独立性：独立资源分配
4. 异步性：相互独立，互不干扰

# 进程与线程

# 线程概念

1. Thread，进程的轻型实体，也叫轻量级进程，是一系列活动按事先设定好的顺序依次执行，是一系列指令的集合
2. 是一条执行的路径，不能单独存在，必须包含在进程中
3. 线程是 OS 中运算调度的最小单位
4. 属性
   1. 轻型实体
   2. 独立调度和分派的基本单位
   3. 可并发执行
   4. 共享进程资源

# 进程和线程的区别

	进程	线程
调度	进程不是调度的基本单位	线程是调度的基本单位
拥有资源	进程拥有资源	线程不拥有资源
并发性	促进并发性	在进程基础上又提高了并发
系统开销	开销大	开销小
地址空间和其他资源	进程间地址空间不共享	同一个进程中的线程共享，不同进程中的线程不可见
通信	进程通信需要辅助	同一个进程中的线程可以实现通信

# 线程的实现方式

# 线程分类

1. 用户级线程（ULT）：User Level Thread
2. 内核级线程（KLT）：Kernel Level Thread

# 进程的运行方式

# 进程的状态

# 进程的生命周期

# 三种基本状态

1. 就绪（Ready）
2. 执行（Running）
3. 阻塞（Blocked）

# 创建和终止状态

1. 创建（New）
2. 终止（Terminated）

# 进程控制

# 进程控制概念

即 OS 对进程实现有效管理，包括创建新进程，撤销已有进程、挂起、阻塞和唤醒、进程切换等多种操作，OS 通过 == 原语（Primitive）== 操作实现进程控制

# 原语的概念

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

# 原语的特点

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

# 进程控制相关原语

1. 创建原语：create
2. 阻塞原语：block
3. 唤醒原语：wakeup
4. 撤销原语：destroy

1. 挂起原语：suspend
   1. 静止就绪：放外存，不调度
   2. 静止阻塞：等待事件
2. 激活原语：active
   1. 活动就绪：等待调度
   2. 活动阻塞：等待唤醒

# 进程的调度

# 处理机调度

1. 概念：根据一定的算法和原则将处理机资源进行重新分配的过程
2. 前提：作业 / 进程数远远大于处理机数
3. 目的：提高资源利用率，减少处理机空闲时间
4. 调度程序：一方面要满足特定系统用户的需求（快速响应），另一方面要考虑系统整体效率（系统平均周转时间）和调度算法本身的开销

# 处理机调度的层次

1. 高级调度 / 作业调度
   1. 把后备作业调入内存
   2. 只调入一次，调出一次
2. 中级调度 / 内存调度
   1. 将进程调至外存，条件合适再调入内存
   2. 在内、外存对换区进行进程调度
3. 低级调度 / 进程调度
   1. 从就绪队列中任取进程分配给处理机
   2. 最基本的调度，频率非常高（相当于一个时间片完成）

# 处理机调度的方式

1. 剥夺式 / 抢占式调度
   1. 立即暂停当前进程
   2. 分配一个处理机给另一个进程
   3. 原则：优先权 / 短进程优先 / 时间片原则
2. 非剥夺式 / 非抢占式调度
   1. 若有进程请求执行
   2. 等待直到当前进程完成或阻塞
   3. 缺点：适用于批处理系统，不适用分时 / 实时系统

# 处理机调度的时机

1. 进程运行完毕
2. 进程时间片用完
3. 进程要求 I/O 操作
4. 执行某种原语操作
5. 高优先级进程申请运行（剥夺式调度）

# 处理机调度的过程

1. 保存镜像：记录进程线程信息
2. 调度算法：确定分配处理机的原则
3. 进程切换：分配处理机给其他进程
4. 处理机回收：从进程回收处理机

# 处理机调度的算法指标

1. CPU 利用率：$忙碌时间/总实现$
2. 系统吞吐量：$完成作业数/总时间$
3. 周转时间：$作业完成时间 - 提交时间$、$带权周转时间=周转时间/实际运行时间$
4. 等待时间：作业等待处理机调度时间
5. 响应时间：提交请求到首次响应间隔

# 调度算法

# 先来先服务（FCFS，FIrst Come First Served）

1. 算法内容：调度作业 / 就绪队列中最先入队者，等待操作完成阻塞
2. 算法规则：按作业 / 进程到达顺序服务
3. 调度方式：非抢占式调度
4. 适用场景：作业 / 进程调度
5. 优缺点：
   1. 有利于 CPU 繁忙型作业，充分利用 CPU 资源
   2. 不利于 I/O 繁忙型作业，操作耗时，其它饥饿

# 短作业优先（SJF，Shortest Job First）

1. 算法内容：所需服务时间最短的作业 / 进程优先服务
2. 算法原则：追求最少的平均周转时间
3. 调度方式：SJF/SPF 非抢占式
4. 适用场景：作业 / 进程调度
5. 优缺点：
   1. 平均等待 / 周转时间最少
   2. 长时间的周转时间会增加或饥饿
   3. 估计时间不准确，不能保证紧迫任务及时处理

# 高响应比优先调度（HRRN，Hightest Response Ratio Next）

1. 算法内容：结合 FCFS 和 SJF，综合等待时间和服务时间计算响应比，高的优先调度
2. 算法规则：综合考虑作业 / 进程的等待时间和服务时间
3. 调度方式：非抢占式
4. 适用场景：作业 / 进程调度
5. 响应比计算：
   1. 响应比 =(等待时间 + 服务时间)/ 服务时间
   2. 只有当前进程放弃执行权时，重新计算所有进程响应比
   3. 长作业等待越久响应比越高，更容易获得处理机

# 优先级调度（PSA，Priority-Scheduling Algorithm）

1. 算法内容：又叫优先权调度，按作业 / 进程的优先级（紧迫程度）进行调度
2. 算法原则：优先级最高（最紧迫）的作业 / 进程先调度
3. 调度方式：抢占 / 非抢占式（并不能获得及时执行）
4. 适用场景：作业 / 进程调度
5. 优先级设置原则：
   1. 静态 / 动态优先级
   2. 系统 > 用户；交互型 > 非交互型；I/O 型 > 计算型
   3. 低优先级进程可能会产生饥饿

# 时间片轮转调度（RR，Round-Robin）

1. 算法内容：按进程到达就绪队列的顺序，轮流分配一个时间片去执行，时间用完则剥夺
2. 算法规则：公平、轮流为每个进程服务，进程在一定时间内都能得到响应
3. 调度方式：抢占式，由时钟中断确定时间到
4. 适用场景：进程调度
5. 优缺点：
   1. 公平，响应快，适用于分时系统
   2. 时间片决定因素：系统响应时间、就绪队列进程数量、系统处理能力
   3. 时间片太大，相当于 FCFS；大小，处理机切换频繁，开销增大

# 多级反馈队列调度（MFQ，Multileveled Feedback Queue）

1. 算法内容：
   1. 设置多个优先级排序的就绪队列优先级从高到低，时间片从小到大新进程采用队列降级法
      1. 进入第一级队列，按 FCFS 分时间片
      2. 没有执行完，移到第二级，第三级
   2. 前面队列不为空，不执行后续队列进程
2. 算法原则：集合前几种算法优点，相当于 PSA+RR
3. 调度方式：抢占式
4. 适用场景：进程调度
5. 优缺点：
   1. 对各类型相对公平，快速响应
   2. 终端型作用用户：短作业优先
   3. 批处理作业用户：周转时间短
   4. 长批处理作业用户：在前几个队列部分执行

# 进程之间如何协作

# 进程通信

# 概念

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

1. 进程是资源分配的基本单位，各进程内存空间彼此独立
2. 一个进程不能随意访问其他进程的地址空间

# 特点

1. 共享存储（Shared-Memory）
2. 信息传递（Message-Passing）
3. 管道通信（Pipe）

# 共享存储（Shared-Memory）

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

# 消息传递（Message-Passing）

1. 直接通信：点到点的发送
   1. 发送和接收时指明双方进程的 ID
   2. 每个进程维护一个消息缓冲队列
2. 间接通信：广播信箱
   1. 以信箱为媒介，作为中间实体
   2. 发进程将信息发送到信箱，收进程从信箱读取
   3. 可以广播，容易建立双向通信链

# 管道通信（Pipe）

1. 管道
   1. 用于连接读 / 写进程的共享文件，pipe 文件
   2. 本质是内存中固定大小的缓冲区
2. 半双工通信
   1. 同一时段只能单向通信，双工通信需要两个管道
   2. 以先进先出（FIFO）方式组织数据传输
   3. 通过系统调用 read ()/write () 函数进行读写操作

# 进程同步

# 同步和互斥的概念

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

1. 前提
   1. 进程是并发执行的，进程间存在着相互制约关系
   2. 并发的进程对系统共享资源进行竞争
   3. 进程通信，过程中相互发送的信号称为信息或事件
2. 两种相互制约形式
   1. 间接相互制约关系（互斥）：进程排他性地访问共享资源
   2. 直接相互制约关系（同步）：进程间的合作，比如管道通信

# 互斥的访问过程

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

# 互斥访问原则

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

# 软件实现互斥的方法

# 软件实现方法

1. 单标志法：违背空闲让进
2. 双标志法先检查：违背忙则等待
3. 双标志法后检查：
   1. 违背空闲让进
   2. 违背有限等待
4. 皮特森算法：
   1. 违背让权等待
   2. 会发生忙等

# 硬件实现互斥的方法

# 中断屏蔽

# 中断屏蔽方法：关中断 / 开中断

1. 禁止一切中断，CPU 执行完临界区之前不会切换
2. 关中断可能被滥用
3. 关中断时间长影响效率
4. 不适用于多处理机，无法防止其它处理机调度其它进程访问临界区
5. 只适用于内核进程（该指令运行在内核态）

# Test-And-Set（TS 指令 / TSL 指令）

1. 读出标志并设置 true，返回旧值，原子操作
2. 也被称为 TSL 指令（Test-And-Set-Lock）
3. 违背让权等待，会发生忙等

# Swap 指令

1. 交换两个变量的值，原子操作
2. 违背让权等待

# 信号量（Sempaphore）

# 信号量机制

1. PV 操作
   1. P 操作：wait 原语，进程等待（荷兰翻译）
   2. V 操作：signal 原语，唤醒等待进程
2. 整型信号量 ：违背让权等待，会发生忙碌
3. 记录型信号量：进程进入阻塞状态，不会忙等

# 管程（Monitor，监视器）

# 定义

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

# 组成

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

# 基本特征

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

# 条件变量 / 条件对象

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

# 处理死锁问题

# 死锁的处理策略

# 死锁的解除

1. 资源剥夺
   1. 挂起死锁进程
   2. 剥夺其资源
   3. 将资源分配给其它进程
2. 撤销进程
3. 进程回退
   1. 回退到足以避免死锁的地步
   2. 需要记录进程历史信息，设置还原点

# 死锁的概念

# 死锁定义

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

# 相关概念：饥饿

等待时间过长以至于给进程推进和响应带来明显影响

# 死锁产生的原因

1. 系统资源的竞争
2. 进程推进顺序非法

# 死锁产生的必要条件

1. 互斥条件：共享资源的排他性访问
2. 不剥夺条件：访问时该共享资源不会被剥夺
3. 请求并保持条件：：保持当前资源时请求另外一个资源
4. 循环等待条件：存在共享资源的循环等待链

# 死锁的预防

# 破坏互斥条件

1. 将只能互斥访问的资源改为同时共享访问
2. 将独占锁改为共享锁
3. 不是所有资源都能改成可共享的

# 破坏不剥夺 / 不可抢占条件

1. 请求新资源无法满足时必须释放已有资源
2. 由 OS 协助强制剥夺某进程持有的资源
3. 实现复杂，代价高
4. 此操作过多导致原进程任务无法推进

# 破坏请求并保持条件

1. 进程开始运行时一次性申请所需资源
   1. 资源浪费
   2. 进程饥饿
2. 阶段性请求和释放资源

# 破坏循环等待条件

1. 对所有资源现行排序，按序号请求资源
   1. 请求时先低再高
   2. 释放时小高再低
2. 对资源的编号应相对稳定，限制了新设备增加
3. 进程使用资源的顺序可能与系统编号顺序不同
4. 限制了用户编程

# 死锁避免

# 安全性算法

1. 系统安全状态
   1. 安全状态一定不会出现死锁
   2. 不安全状态可能出现死锁
2. 银行家算法
   1. 系统预判进程请求是否导致不安全状态
   2. 是则拒绝请求，否则答应请求

# 死锁检测与解除

# 死锁检测

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

# 死锁解除

1. 剥夺资源
2. 撤销进程
3. 进程回退