一.什么是进程
进程概念：
进程（Process），是一个具有必定独立功用的程序关于某个数据调集的一次运转活动，是体系进行 『资源分配和调度』 的一个独立单位。
进程的结构
- 操控块（PCB）：进程唯一标识
- 数据段：存放原始数据与中心数据
- 程序段：存放在文本区域，可被多个进程同享
进程的特征
- 动态性：由创立而生，由吊销而亡
- 并发性：多个进程一起运转
- 独立性：独立资源分配
- 异步性：彼此独立、互不干扰
进程与线程
什么是线程？
- Thread，进程的轻型实体，也叫“轻量级进程”，是一系列活动按事前设定好的次序顺次履行的进程，是一系列指令的调集
- 是一条履行途径，不能独自存在，有必要包括在进程中
- 线程是OS中运算调度的最小单位
为什么引入线程？： 进步OS的并发性
线程的特色
- 轻型实体
- 独立调度和分派的根本单位
- 可并发履行
- 同享进程资源
线程的实现办法
- 用户级线程
- 内核级线程
总结：
二.进程是怎样运转的
进程的状态
- 安排妥当（Ready）
- 履行（Running）
- 堵塞（Blocked）
- 创立（New）
- 停止（Terminated）
进程操控
即OS对进程实现有效的管理，包括创立新进程、吊销已有进程、挂起、堵塞和唤醒、进程切换等多种操作。OS经过 原语（Primitive） 操作实现进程操控。
那么原语是什么？（前文复习）
由若干条指令组成，完结特定的功用，是一种原子操作（Action Operation）
特色：
- 原子操作，要么全做，要么全不做，履行进程不会被中止
- 在管态/体系态/内核态下履行，常驻内存
- 是内核三大支撑功用（中止处理/时钟管理/原语操作）之一
进程操控中的原语操作：
根本操作原语
- 创立原语：create
- 堵塞原语：block
- 唤醒原语：wakeup
- 吊销原语：destroy
操作如图：
挂起与激活原语
为了体系和用户调查和分析进程
- 挂起原语： suspend
- 静止安排妥当：放外存，不调度
- 静止堵塞：等候事情
- 激活原语：active
- 活动安排妥当：等候调度
- 活动堵塞：等候唤醒
处理机调度
根据必定的算法和准则将处理机资源进行从头分配的进程。
条件：作业/进程数远远大于处理机数
目的：进步资源使用率，削减处理机闲暇时刻
调度程序：一方面要满足特定体系用户的需求（快速呼应），另一方面要考虑体系全体功率（体系均匀周转时刻）和调度算法自身的开支
调度的层次
高档调度/作业调度
- 把后备作业调入内存
- 只调入一次，调出一次
中级调度/内存调度
- 将进程调至外存，条件适宜再调入内存
- 在内、外存对换区进行进程对换
初级调度/进程调度
- 从安排妥当行列选取进程分配给处理机
- 最根本的调度，频率非常高（相当于一个时刻片完结）
调度办法
掠夺式/抢占式调度
- 立即暂停当时进程
- 分配处理机给另一个进程
- 准则：优先权/短进程优先/时刻片准则
非掠夺/非抢占式调度
- 若有进程恳求履行
- 等候直到当时进程完结或堵塞
- 缺陷：适用于批处理体系，不适用分时/实时体系
调度机遇
- 进程运转结束
- 进程时刻片用完
- 进程要求I/O操作
- 履行某种原语操作
- 高优先级进程申请运转（掠夺式调度）
调度进程
- 保存镜像：记载进程现场信息
- 调度算法：确定分配处理机的准则
- 进程切换：分配处理机给其它进程
- 处理机回收：从进程收回处理机
调度算法
先来先服务（FCFS)
算法内容：调度作业/安排妥当行列中最先入队者，等候操作完结或堵塞
算法准则：按作业/进程抵达次序服务（履行）
调度办法：非抢占式调度
适用场景：作业/进程调度
优缺陷：
有利于CPU繁忙型作业，充分使用CPU资源
不利于I/O繁忙型作业，操作耗时，其它饥饿
短作业优先(SJF)
算法内容：所需服务时刻最短的作业/进程优先服务（履行）
算法准则：追求最少的均匀（带权）周转时刻
调度办法：SJF/SPF非抢占式
适用场景：作业/进程调度
优缺陷：
均匀等候/周转时刻最少（算法准则）
长作业周转时刻会添加或饥饿
估计时刻不准确，不能保证急迫任务及时处理
高呼应比优先调度(HRRN)
算法内容：结合FCFS和SJF，归纳考虑等候时刻和服务时刻核算呼应比，高的优先调度
算法准则：归纳考虑作业/进程的等候时刻和服务时刻
调度办法：非抢占式
适用场景：作业/进程调度
呼应比核算： 呼应比=(等候时刻+服务时刻)/服务时刻, ≥1 只要当时进程放弃履行权（完结/堵塞）时，从头核算全部进程呼应比 长作业等候越久呼应比越高，更简单取得处理机
优先级调度（PSA)
算法内容：又名优先权调度，按作业/进程的优先级（急迫程度）进行调度
算法准则：优先级最高（最急迫）的作业/进程先调度
调度办法：抢占/非抢占式（并不能取得及时履行）
适用场景：作业/进程调度
优先级设置准则：
- 静态/动态优先级
- 体系>用户；交互型>非交互型；I/O型>核算型
- 低优先级进程或许会发生“饥饿”
时刻片轮转调度(RR)
算法内容：按进程抵达安排妥当行列的次序，轮番分配一个时刻片去履行，时刻用完则掠夺
算法准则：公正、轮番为每个进程服务，进程在必定时刻内都能得到呼应
调度办法：抢占式，由时钟中止确定时刻到
适用场景：进程调度
优缺陷：
公正，呼应快，适用于分时体系（人人都有饭吃）
时刻片决定因素：体系呼应时刻、安排妥当行列进程数量、体系处理才能
时刻片太大，相当于FCFS；太小，处理机切换频繁，开支增大
多级反应行列调节(MFQ)
算法内容：
- 设置多个按优先级排序的安排妥当行列
- 优先级从高究竟，时刻片从小到大
- 新进程选用行列降级法
- 进入第一级行列，按FCFS分时刻片
- 没有履行完，移到第二级，第三级。。。
- 前面行列不为空，不履行后续行列进程
算法准则：集前几种算法优点，相当于PSA+RR
调度办法：抢占式
适用场景：进程调度
优点：
- 对各类型相对公正；快速呼应；
- 终端型作业用户：短作业优先
- 批处理作业用户：周转时刻短
- 长批处理作业用户：在前几个行列部分履行
总结
进程之间是怎样协作的
进程通讯
概念：进程通讯即进程间的信息交流
进程是资源分配的根本单位，各进程内存空间彼此独立
一个进程不能随意拜访其它进程的地址空间
特色：
- 同享存储（Shared-Memory）
- 消息传递（Message-Passing）
- 管道通讯（Pipe）
同享存储
根据同享数据结构的通讯办法
- 多个进程共用某个数据结构（OS供给并操控）
- 由用户（程序员）担任同步处理
- 初级通讯：能够传递少量数据，功率低
根据同享存储区的通讯办法
- 多个进程共用内存中的一块存储区域
- 由进程操控数据的形式和办法办法
- 高档通讯：能够传递很多数据，功率高
消息传递
直接通讯：点到点发送
- 发送和接纳时指明两边进程的ID
- 每个进程保护一个消息缓冲行列
直接通讯：播送信箱
- 以信箱为媒介，作为中心实体
- 发进程将消息发送到信箱，收进程从信箱读取
- 能够播送，简单建立双向通讯链
管道通讯
管道
- 用于衔接读/写进程的同享文件，pipe文件
- 本质是内存中固定大小的缓冲区
半双工通讯
- 同一时段只能单向通讯，双工通讯需求两个管道
- 以先进先出（FIFO）办法安排数据传输
- 经过体系调用read()/write()函数进行读写操作
进程同步
和谐进程间的彼此约束联系，使它们按照预期的办法履行的进程
条件
- 进程是并发履行的，进程间存在着彼此约束联系
- 并发的进程对体系同享资源进行竞赛
- 进程通讯，进程中彼此发送的信号称为消息或事情
两种彼此约束形式
- 直接彼此约束联系（互斥）：进程排他性地拜访同享资源
- 直接彼此约束联系（同步）：进程间的协作，比方管道通讯
互斥的拜访临界资源
拜访进程
- 进入区：测验进入临界区，成功则加锁（lock）
- 临界区：拜访同享资源
- 退出区：解锁（unlock），唤醒其它堵塞进程
- 剩下区：其它代码
拜访准则
- 闲暇让进：临界区闲暇，允许一个进程进入
- 忙则等候：临界区已有进程，其它进程等候（堵塞状态）
- 有限等候：处于等候的进程，等候时刻有限
- 让权等候：等候时应让出CPU履行权，避免“忙等候”
软件实现办法
- 单标志法：违反“闲暇让进”
- 双标志法先查看
- 双标志法后查看
- 皮特森算法（Peterson’s Algorithm）
单标志法：违反“闲暇让进”
双标志法先查看：违反“忙则等候”
双标志法后查看：违反“闲暇让进”，“有限等候”
皮特森算法：违反“让权等候”，“忙等”
- 中止屏蔽办法：关中止/开中止
- 制止全部中止，CPU履行完临界区之前不会切换
- 关中止或许会被乱用
- 关中止时刻长影响功率
- 不适用于多处理机，无法避免其它处理机调度其它进程拜访临界区
- 只适用于内核进程（该指令运转在内核态）
Test-And-Set（TS指令/TSL指令）
- 读出标志并设置为true，回来旧值，原子操作
- 也被称作TSL指令（ Test-And-Set-Lock ）
- 违反“让权等候”，会发生忙等
Swap指令（ EXCHANGE，XCHG指令）
- 交流两个变量的值，原子操作
- 违反“让权等候”
信号量（Semaphore）机制
PV操作：
- P操作：wait原语，进程等候
- V操作：signal原语，唤醒等候进程
整型信号量：违反“让权等候”，会发生忙等
记载型信号量：进程进入堵塞状态，不会忙等
管程（Monitor，监视器）
“管理进程”，即用于实现进程同步的工具。是由代表同享资源的数据结构和一组进程（进行PV操作的函数）组成的管理程序（封装）。
管程的组成
- 管程称号
- 部分于管程内部的同享数据结构
- 对该数据结构操作的一组进程（函数）
- 管程内同享数据的初始化句子
管程的根本特性
- 是一个模块化的根本程序单位，能够独自编译
- 是一种抽象数据类型，包括数据和操作
- 信息掩蔽，同享数据只能被管程内的进程拜访
条件变量/条件对象
- 进入管程的进程或许因为条件不满足而堵塞
- 此时进程应开释管程以便其它进程调用管程
- 进程被堵塞的条件（原因）有多个，移入不同的条件行列
- 进程被移入条件行列后，应开释管程
总结
四.怎么处理死锁问题
死锁的概念
死锁界说：多个进程因为竞赛资源而形成的堵塞现象，若无外力作用，这些进程将无法继续推动。
相似概念：饥饿 等候时刻过长以至于给进程推动和呼应带来显着影响，“饿而不死” 死锁发生的原因
- 体系资源的竞赛
- 进程推动次序非法 死锁发生的必要条件 互斥条件：同享资源的排他性拜访 不掠夺条件：拜访时该同享资源不会被掠夺 恳求并保持条件：保持当时资源时恳求另一个资源 循环等候条件：存在同享资源的循环等候链
死锁的处理战略
死锁预防
损坏互斥条件
- 将只能互斥拜访的资源改为一起同享拜访
- 将独占锁改为同享锁
- 缺陷：不是全部资源都能改成可同享的
损坏不掠夺/不行抢占条件
- 恳求新资源无法满足时有必要开释已有资源
- 由OS帮忙强制掠夺某进程持有的资源
缺陷：
- 实现复杂，代价高
- 此操作过多导致原进程任务无法推动
损坏恳求并保持条件
进程开始运转时一次性申请所需资源
缺陷：
- 资源糟蹋
- 进程饥饿
阶段性恳求和开释资源
损坏循环等候条件
对全部资源现行排序，按序号恳求资源
- 恳求时先低再高
- 开释时先高再低
缺陷：
- 对资源的编号应相对稳定，约束了新设备添加
- 进程运用资源的次序或许与体系编号次序不同
- 约束了用户编程
死锁避免
安全性算法
体系安全状态
- 安全状态必定不会出现死锁
- 不安全状态或许出现死锁
银行家算法
- 体系预判进程恳求是否导致不安全状态
- 是则拒绝恳求，否则答应恳求
死锁的检测与解除
死锁检测
- 需求一种数据结构，保存有关资源的恳求和分配信息
- 供给一种算法，使用这些信息检测是否形成了死锁
死锁解除
- 资源掠夺
- 吊销进程
- 进程回退
死锁的检测
资源分配图（G=(N, E)）：
- 两种资源
- 两种节点
死锁定理（死锁状态的充分条件）：
- 当且仅当此状态下资源分配图是不行完全简化的
- 简化进程类似于“拓扑排序”算法（注意数据结构考察）
死锁的解除
资源掠夺
- 挂起死锁进程
- 掠夺其资源
- 将资源分配给其它（死锁）进程
吊销进程
进程回退
- 回退到足以避免死锁的境地
- 需求记载进程前史信息，设置还原点
总结
